[go-nuts] Feature Idea: automagically switch slice backing to array of arrays as required.

Hi Simon,

Your proposal is lacking one thing, a problem statement. That is, what
is difficult/hard/impossible/slow/etc today that your proposal is
attempting to rectify.

Cheers

Dave

On Thu, Nov 21, 2013 at 10:32 AM, simon place
wrote:

sorry bit hidden, too cut down on array copying.

worst case would be: very large but unknown size data set, reach the limit
you guessed, so currently have to copy it all, and isn't this really a
killer problem if you get anywhere near half your memory in that slice.

It sounds like what you're describing is transparent support for slices
which can be spread over multiple backing arrays simultaneously. For
example, `append([]int{1,2,3}, 4, 5, 6)` could return an array which would
effective have an (augmented slice header of):

ptr = [][]int{[]int{1, 2, 3}, []int{4, 5, 6}}
len = 6
cap = 6

If that's the proposal, then there are several benefits and practical
drawbacks involved (particularly when the phrase "automatic" is involved):

benefits:

    - "copying" is avoided
    - less garbage is generated in naive application use cases.

drawbacks:

    - allocations aren't reduced
    - memcpy operations are fast even on old processors, so copying is less
    of a bottleneck then it would appear to be.
    - slice headers would become substantially more complex
    - if the mechanism is "automatic", expect to break to completely syscall
    (including any use of file/net i/o) and C compatibility, unless automatic
    as-needed copying is done at these boundaries or "escapes Go" analysis
    prevents use of this mechanism in such cases.
    - data locality is reduced and an extra indirection would always be
    required: in pathological cases, this could lead to worse allocate+access
    performance than the current allocate+copy+(trash)+access performance.
    - it's already trivial to implement this kind of structure on an
    as-needed basis, so there's much less benefit to making it part of the core
    language. "large" applications will have already implemented this or
    another reasonable custom "allocator" (or growth will flatten out and
    initial garbage will be inconsequential), while small applications will not
    be processing enough data for the benefits or drawbacks of either this or
    the current default approach to make any difference.

that's basically it, and i did notice most of the cons you mention, only...
see below for my thinking.
i think the "automatic" actually solves the main drawbacks, mostly because
its effectively controlled by the slices capacity parameter.

even impossible, requiring custom solutions which then bar direct use with
std libs, and other code.

also can you assume all go architectures will
have sophisticated, hardware accelerated, virtual memory systems? (a real
question here, im not sure, but would guess some embedded stuff would be
very slow at this.)

    - slice headers would become substantially more complex

only 'switched on' when benefits are large.
could prevent it when you were exposing implementation externally, (not an
ideal thing to be doing anyway, experts only?).
transitory, used when needed, and although automatic, deterministic and
avoidable as a programming choice. i think fixed array of arrays backing
wouldn't be worth the trouble.

    - it's already trivial to implement this kind of structure on an
    as-needed basis, so there's much less benefit to making it part of the core
    language. "large" applications will have already implemented this or
    another reasonable custom "allocator" (or growth will flatten out and
    initial garbage will be inconsequential), while small applications will not
    be processing enough data for the benefits or drawbacks of either this or
    the current default approach to make any difference.

the point is that the array of array backing comes in in rare cases, as a
choice, but works transparently with existing code, cant do that with
custom solutions. If the underlying functional requirement is the same, but
is being rewritten many times, many ways, it should be in the language, to
cut down effort/bugs and increase code reuse.
Ideally this feels like at should be a add-in lib, so directly and
explicitly a programmers choice, but cant do that in Go.

I've always found the implicit allocation and copying to be predictable --
it really only happens when append is used or []byte <-> string conversions
occur, and in the stdlib and elsewhere, allocating appends to
application-provided data are rare except when the API either takes and
returns a slice, or takes a pointer to a slice. The exception to this rule
is if the library uses or implements "second order allocators", thus having
the property of negligible garbage generation.

don't understand 'naive'
>

In this and similar contexts, 'naive' can mean either wasteful or
pragmatic: the former in cases where the application generates a lot of
garbage that it doesn't need to, such as by excessively converting []byte
to string when equivalent []byte APIs are available, or making
theoretically ideal but practically deficient design choices such as use of
container/list when slices are actually more appropriate; the latter case
applies when the nature of the application (or a portion thereof) does not
demand special consideration toward limiting garbage generation, such as in
a copying string conversion that only occurs once, or when the entire
application can be expected to complete before the first GC cycle
occurs--in these situations, it's entirely reasonable to sacrifice
hypothetical performance in order to write more code more quickly.

Here in particular, I mean that applications which don't manage and re-use
their own slices (either because the programmer doesn't know better, or
because knowing better made them decide it wasn't important), with your
proposal, will in append-heavy situations have the same number of
allocations, but those allocations will be slightly smaller, and fewer or
none of those allocations would end up being garbage on the next append.
  Note that with Go's GC, it's is the number of allocations (fewer is
better), rather than the size of allocations, that primarily figures into
GC efficiency.

Do any such cases come to mind? When append needs to allocate and copy a
slice of *any* type, a highly optimized, hardware accelerated copy is used
(it doesn't matter that the slice/array element type might not be byte).

At the moment... kinda, yeah. The vector instruction(s) that are used for
large block copies are conceptually and behaviorally very simple, and on
some level very fundamental to just about any non-trivial application that
has been written in the last couple of decades; it seems likely that even
mis-designed, custom-purpose stripped-down chipsets of any architecture
will either have support for this kind of operation, or will be limited to
on-die memory whilst having no instruction cache or prediction (in which
case vector ops would be no faster than non-vector equivalents, making them
pointless).

On embedded systems, virtual memory systems/controllers may not exist, and
so Go can't run on those systems with its default runtime; you would need
something like https://code.google.com/p/tinygo/ in that case, which is
designed to run in the absence of a host OS (and where there are no other
applications running, thus no need to virtualize memory on the hardware
level since there's nobody to 'share' physical memory with). Anyone
planning to deploy Go on such systems already knows what to expect, and
anyone who doesn't know what to expect from these systems certainly won't
be deploying to them.

The contextual switching is the primary contributor to this complexity, not
the actual structure of such augmented slice headers; here, simplicity
cannot be had without predictability, and predictability is difficult to
achieve (if at all) without re-basing your proposal on a new, explicit
(visibly different) slice variant type 'kind'.
I see this as the such a serious drawback that it's really the only issue
of consequence: if you can figure out a way to 1) avoid breakage, while 2)
making it all automatic (implicit and indistinguishable, both in the code
and in the runtime), then you'd really only have to deal with the typical
"is it worth the five lines it adds to the spec?" counter arguments. You
could also solve this by making it explicit (non-automatic) as mentioned
above.

i envisaged array of arrays backing to be numerically very rare and often
I don't understand what you mean by this. Please elaborate.

the point is that the array of array backing comes in in rare cases, as a
For better or worse, it's common, easy, and often encouraged to reinvent
the wheel in Go (at the expense of code reuse) when 1) the estimated time
involved in implementing that wheel is less than the expected time involved
in finding, evaluating, and integrating approriate pre-existing wheel
designs, or 2) a custom wheel is necessarily faster, simpler, smaller, or
better than any already available more generalized wheels, as long as 3)
the likelyhood of creating bugs in the new design, and the associated risk
of those bugs, does not outweigh points 1 or 2.

I've run into plenty of cases where unmanaged append behavior is
undesirable (particularly the allocations, not necessarily the copying),
however, in my experience it has been rare that the ideal
allocation/memory-management strategy is precisely the same between
multiple applications, and it has also been rare that the individual, ideal
solutions have been difficult or time consuming to implement. I haven't had
an application in which your proposed case is ideal, but I can think of a
number of situations in which it or a variation on it would be, though I do
feel as though I could have implemented a half-dozen bug-free custom
realizations of the general concept in the time spent writing this reply.

i see, so better for novice users, but not experienced ones, yes would
agree .

but, there will always be cases, where copying is massively slower, or even
i was thinking any type, didn't see what difference it make for this.

also can you assume all go architectures will
so potentially much faster on these.
(see next post)

i envisaged array of arrays backing to be numerically very rare and often
in a common scenario, processing a stream, i can envisage only very few
slices backed by AOA, and they come and go, ie you have them for a
transition over the boundary and then go back to normal, transparently, the
implementation effectively deals with the interface between fixed length
buffers and continuous processing. (probably really should have demo code
for this.)

the point is that the array of array backing comes in in rare cases, as a
easily documented/explained?

Currently it's specified as a runtime error (and it never can be purely a
compile-time error). As such, you can't change out-of-bounds slicing
semantics while being transparently compatible with all existing programs.
You could potentially get away with adding a new builtin to cover this
functionality, or modifying append to use the new mechanism under certain
conditions. Unless people *really* know what they're doing, they don't
slice into capacity (or in your case, slice past capacity) to indicate that
they want to append... they use append. I believe the most
beginner-friendly outlet for the idea is to modify append, even if there
were no definite compatibility issues arising from slicing past capacity.

Not sure what you're getting at here -- the difference between slices and
arrays in Go is not that one has fixed length, but rather than one is a
reference and the other is a direct value. If you say [32]byte, it'll
generally be stack allocated (unless a pointer to it *could* escape to the
heap, in which case it is allocated the same way that a call to make would
be). Conversely, a non-escaping make([]byte, 32) will be stack allocated,
since its size is known at compile time.

Slices should really be used when you're using a variable
Because of the above, the choice between slices and arrays here isn't
particularly important. Being a direct value, arrays can be used as map
keys or tested for equality (assuming that the element type is comparable),
while slices cannot on the language level.

i see, so better for novice users, but not experienced ones, yes would
*Marginally* better, in a "saving them from themselves" sense. If they
don't want to move beyond that level of insufficiency, then this is hardly
the only place their code will suffer. On the other hand, for experienced
users intentionally writing suboptimal code in order to maximize
"programmer productivity", that part of the code will surely be
inconsequential, with no noticeable difference between optimal and
suboptimal (regardless of the underlying mechanism).

The other tradeoff with this is that because of the above-noted
incompatibilities, and the necessary special handling of anything that will
be passed to C or the kernel or whatever, any gains for novices may become
confusion points for intermediates, kind of like C++ has to deal with
regarding their handful of subtle reference types and memory management
strategies.

While Go may be a good learning language, it was designed by experienced
engineers for experienced engineers: for a given language modification to
be warranted, it has to be demonstrated that it is useful to seasoned
programmers, or at least doesn't make their lives any harder. With this
being proposed as an automatic mechanism, in many cases it can make
perfectly legitimate low level uses of slices harder or less predictable
without providing anything that low level programmers aren't already
providing for themselves; if it weren't an automatic mechanism, it wouldn't
make veterans' lives' harder, but it would no longer be as beneficial to
novices. There may be a middle ground, but it has yet to be demonstrated.

To confirm that copy performance is high irrespective of element type, and
doesn't need any recently invented instructions to achieve that
performance: <https://gist.github.com/extemporalgenome/7634394>. Even on an
old netbook, copies can churn 1GiB/s throughput, and with the memory on
that system being 2GiB, the largest possible copy that could remain
entirely within ram, on that machine, could occur in one second. Newer
and/or higher powered machines will have considerably faster performance in
this regard. In general, since append heuristically doubles capacity during
each growth cycle, and application will generally exhaust available ram
before before copy performance becomes problematic for non-critical
applications, and critical applications on expensive hardware where these
copies could be a problem will generally be written to preallocate the
necessary amount of space.

If there are no specific examples in which copying could be massively
slower or impossible, it sounds like this is now a hypothetical, rather
than practical or theoretical, issue.

so potentially much faster on these.
>

That's not what I was implying. And in the case of hardware lacking memory
virtualization capabilities, as long as tinygo, for example, is "the
operating system", then it should have absolutely no bearing on
performance; all else being equal, the lack of memory virtualization (or at
least the absence of memory traps) might actually make memory accesses
(including copying) faster.

in a common scenario, processing a stream, i can envisage only very few
Any kind of efficiency in stream processing really needs to operate within
a fixed (or upper-bounded) window size, or at least should eagerly process
data as it flows through in anticipation that processing will be
successful. This isn't an issue with copying (which doesn't apply to your
proposal), or allocations (which applies equally to your proposal), but
rather unbounded growth; I would recommend neither unbounded use of your
proposal, nor unbounded use of append as a solution for any kind of
continuous stream processing with variable size inputs; bounded uses of
either approach are appropriate and have no meaningful differences from
each other. As an example, if you're parsing data out of lines with
arbitrary length, with one record per line, the naive approach would be to
use something like bufio.Reader's ReadBytes('\n') to get the line, then
process the data within that line. The non-naive approach would be to
process data in fixed-sized chunks, and check each chunk for the presence
of '\n'. Usually there are more convenient ways to achieve this effect
while still maintaining both control and efficiency, such that manual
management of chunks is not an application concern.

By definition they are not intended for reuse if they are purpose-built for
a specific task, though as mentioned before, while reusability is favored
in general contexts, it's more common in Go than in some other "large
scale" languages to favor task-specific implementations at the expense of
reusability.

The maintainability and readability/explainability of such custom code
depends both on how well it was written, and how far the already-available
solution's assumptions deviate from the task at hand. The Go stdlib in many
places avoids convenient (for the user) assumptions in order to keep
functionality simple and flexible, so for many tasks, much or all of the
implementation can be found within the stdlib or similarly written
libraries even if it means the application code needs to do some of its own
initialization to make up for the lack of said assumptions. However,
existing "reusable" code which needs significant shimming to solve a
specific task may require more documentation just to explain *why all the
shims exist* than a well designed custom solution would need to document
the what the whole of the code is doing. Similarly, mis-assuming general
solutions often must be replaced with other mis-assuming general solutions
(and subsequently re-shimmed) as application requirements change, leading
to considerably more overall effort than just tweaking custom solutions.
Also remember that I claimed that there are many situations in which it is
quicker to completely write a correct custom solution than it is find,
evaluate, and integrate general solutions.

arrrr yes, relying on the error, not something i think of ever doing, but
it obviously could be. (but since 1.2 isn't out yet, not at the moment.)

disagree with that completely, slices are variable length, think of the
idiomatic usage, re-slicing to the same name.(like append)

Slices should really be used when you're using a variable
see previous

i see, so better for novice users, but not experienced ones, yes would
i wouldn't have said go was a good learning language, to close to the metal.

i don't see how type effects anything, and examples were previously
provided.

so potentially much faster on these.
you need to be more succinct, this is starting to sound like someone trying
to persuade themselves. sorry but that's my current impression, so please
stop commenting.

"relying on the error" sounds like you're talking about bad code that
intentionally causes an out-of-bounds panic as some control flow mechanism
-- yes, that would be bad code. I'm talking about the runtime choosing to
cause a panic rather than allow undefined behavior to occur. Array/slice
indices can be grouped into three intervals: below bounds (less common), in
bounds, and above bounds (more common). This proposal changes the meaning
of the above-bounds interval, so that what had been a panic will now be an
implicit allocation, which can mask the presence of the bug.

To be clear, this proposal as-specified would definitely be a breaking
language change, and that breakage has nothing to do with version 1.2. The
proposal could be revised so as to make it non-breaking as far as the
language was concerned, but that still wouldn't prevent the cgo/syscall
breakages that the underlying mechanism guarantee... at least not without a
lot of compensatory *copying* to re-pack all the sub-arrays at those call
sites.

To elaborate, "the real value of arrays" is that they're values, not that
they're fixed length; the string type has variable length, but would be
useless if not comparable. Certainly the real value of slices is that they
are variable length (and that they're in the family of reference types).

This was meant to be taken in the context of the specific example, not as
pertaining to arrays vs slices in general throughout all time and space.

All I see is the "half of memory append" problem, which is arbitrary since
constant factors are algorithmically inconsequential. So with your approach
the augmented slice can grow in-place once more, but then you invariably
reach the same out-of-memory problem again. If it were a linear or
super-linear factor, then it'd be worth discussing. Explicit solutions to
this aspect of memory management are rather painless in Go.


Or perhaps you mistakenly expected Go to have arrived at the same notion of
"conventional wisdom" as <insert familiar language here> (namely that
"complete and unconditional avoidance of NIH" is the only wisdom). I'll not
contest the 'succinct' part.

so please stop commenting.


As you wish, I'll let this thread die.

no existing code is effected in that it cant make these as is, you have to
ask for a capacity beyond the current backing array, which is an error
currently, but you will be able to take the new AOA backed slices and fire
them into existing code, (the real point) but surely the slice code is
localised and can hide its implementation here, so its only the externally
exposed implementation calls that are the issue.

but aren't these generally going to be fixed length, and so should be using
arrays not slices, although i can see that that wont always be the case,
handing over a particular part of an array, using a slice to define it,
could be unfortunately common.

Slices should really be used when you're using a variable
length paradyne and then, externally, going thought a fixed length buffer,
so generally going to have to be chunking somewhere anyway, chunking a
array of arrays doesn't seem that difficult in code that is already
re-chunking, isn't it basically just a loop?

Hey Simon,

You can't do it and make it look like a slice, but you can do it using your
own types and methods.

I can think of one very useful use case for this, and that's when you are
dealing with very large byte arrays. (where the copy is expensive) In that
case you can use the io library's MultiReader:

http://golang.org/pkg/io/#MultiReader

This also works well for files where you can avoid having to load the whole
thing into memory before processing it.

this would have to be language change, (although non-breaking)