FAQ
so that, if you were to slice with a capacity (not length) beyond the
parents backing capacity, the new slice that is created would be backed by
an array of the original/parents backing and a newly created array.

then if you were to slice that slice only from items within the
extended/new array, that 'child' slice would again be backed by a single
array.

this means that when all slices backed by the original array, and slices
having that original array in their array of arrays, have all been
dereferenced, that original array can be GC'ed, and so you can carry on
indefinitely avoiding array copying AND still use existing code/std lib,
transparently.

optimisation:

if the last reference to a backing array is lost, in the same instruction
as a slice beyond current capacity, then it might be possible to simply
reused it.





--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Dave Cheney at Nov 20, 2013 at 11:49 pm
    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:
    so that, if you were to slice with a capacity (not length) beyond the
    parents backing capacity, the new slice that is created would be backed by
    an array of the original/parents backing and a newly created array.

    then if you were to slice that slice only from items within the extended/new
    array, that 'child' slice would again be backed by a single array.

    this means that when all slices backed by the original array, and slices
    having that original array in their array of arrays, have all been
    dereferenced, that original array can be GC'ed, and so you can carry on
    indefinitely avoiding array copying AND still use existing code/std lib,
    transparently.

    optimisation:

    if the last reference to a backing array is lost, in the same instruction as
    a slice beyond current capacity, then it might be possible to simply reused
    it.





    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 20, 2013 at 11:58 pm
    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Kevin Gillette at Nov 21, 2013 at 12:56 am
    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.

    On Wednesday, November 20, 2013 4:32:03 PM UTC-7, simon place wrote:

    so that, if you were to slice with a capacity (not length) beyond the
    parents backing capacity, the new slice that is created would be backed
    by an array of the original/parents backing and a newly created array.

    then if you were to slice that slice only from items within the
    extended/new array, that 'child' slice would again be backed by a single
    array.

    this means that when all slices backed by the original array, and slices
    having that original array in their array of arrays, have all been
    dereferenced, that original array can be GC'ed, and so you can carry on
    indefinitely avoiding array copying AND still use existing code/std lib,
    transparently.

    optimisation:

    if the last reference to a backing array is lost, in the same instruction
    as a slice beyond current capacity, then it might be possible to simply
    reused it.



    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 21, 2013 at 3:31 am
    that's basically it, and i did notice most of the cons you mention, only...
    see below for my thinking.
    On Thursday, 21 November 2013 00:56:25 UTC, Kevin Gillette wrote:

    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):
    i think the "automatic" actually solves the main drawbacks, mostly because
    its effectively controlled by the slices capacity parameter.

    benefits:

    - "copying" is avoided

    this is also good because the current level of copying, is
    surprising.(even when not inefficient)
    - less garbage is generated in naive application use cases.

    don't understand 'naive'
    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.

    but, there will always be cases, where copying is massively slower, or
    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.
    - 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.

    true, but you (programmer) know when this can not have happened, and so
    could prevent it when you were exposing implementation externally, (not an
    ideal thing to be doing anyway, experts only?).
    - 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.

    i envisaged array of arrays backing to be numerically very rare and often
    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Kevin Gillette at Nov 21, 2013 at 12:25 pm

    On Wednesday, November 20, 2013 8:31:26 PM UTC-7, simon place wrote:

    this is also good because the current level of copying, is
    surprising.(even when not inefficient)
    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.

    but, there will always be cases, where copying is massively slower, or
    even impossible, requiring custom solutions which then bar direct use with
    std libs, and other code.
    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).

    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.)
    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.

    - slice headers would become substantially more complex

    only 'switched on' when benefits are large.
    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'.
    - 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.

    true, but you (programmer) know when this can not have happened, and so
    could prevent it when you were exposing implementation externally, (not an
    ideal thing to be doing anyway, experts only?).
    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
    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.
    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
    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.
    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 24, 2013 at 7:33 pm

    On Thursday, 21 November 2013 12:25:17 UTC, Kevin Gillette wrote:
    On Wednesday, November 20, 2013 8:31:26 PM UTC-7, simon place wrote:

    this is also good because the current level of copying, is
    surprising.(even when not inefficient)
    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.
    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
    impossible, requiring custom solutions which then bar direct use with std
    libs, and other code.
    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).
    i was thinking any type, didn't see what difference it make for this.

    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.)
    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.
    so potentially much faster on these.
    - slice headers would become substantially more complex

    only 'switched on' when benefits are large.
    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'.
    - 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.

    true, but you (programmer) know when this can not have happened, and so
    could prevent it when you were exposing implementation externally, (not an
    ideal thing to be doing anyway, experts only?).
    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.
    (see next post)

    i envisaged array of arrays backing to be numerically very rare and often
    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.
    I don't understand what you mean by this. Please elaborate.
    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
    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.
    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.

    would those custom realizations be as maintainable, reusable, and as
    easily documented/explained?

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Kevin Gillette at Nov 25, 2013 at 3:09 am

    On Sunday, November 24, 2013 1:11:39 PM UTC-7, simon place wrote:
    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.
    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.

    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.
    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
    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?
    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
    agree.
    *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.

    but, there will always be cases, where copying is massively slower, or
    even impossible, requiring custom solutions which then bar direct use with
    std libs, and other code.
    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).
    i was thinking any type, didn't see what difference it make for this.
    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
    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.)
    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.

    would those custom realizations be as maintainable, reusable, and as
    easily documented/explained?
    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 26, 2013 at 9:01 pm

    On Monday, 25 November 2013 03:09:49 UTC, Kevin Gillette wrote:
    On Sunday, November 24, 2013 1:11:39 PM UTC-7, simon place wrote:

    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.
    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.
    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.)

    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.
    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.
    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
    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?
    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.
    see previous

    i see, so better for novice users, but not experienced ones, yes would
    agree.
    *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.
    i wouldn't have said go was a good learning language, to close to the metal.

    but, there will always be cases, where copying is massively slower, or
    even impossible, requiring custom solutions which then bar direct use with
    std libs, and other code.
    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).
    i was thinking any type, didn't see what difference it make for this.
    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.
    i don't see how type effects anything, and examples were previously
    provided.

    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
    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.)
    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.

    would those custom realizations be as maintainable, reusable, and as
    easily documented/explained?
    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.


    this just seems mistaken to me, if i understand the argument right, and
    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Kevin Gillette at Nov 27, 2013 at 3:16 am

    On Tuesday, November 26, 2013 2:01:37 PM UTC-7, simon place wrote:

    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.)
    "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.

    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.
    disagree with that completely, slices are variable length, think of the
    idiomatic usage, re-slicing to the same name.(like append)
    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).

    Because of the above, the choice between slices and arrays here isn't
    particularly important.
    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.

    examples were previously provided.
    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.

    this just seems mistaken to me, if i understand the argument right, and
    you need to be more succinct, this is starting to sound like someone trying
    to persuade themselves. sorry but that's my current impression

    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.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 24, 2013 at 8:11 pm

    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.
    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?




    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Caleb Doxsey at Nov 21, 2013 at 3:10 pm
    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.
    On Wednesday, November 20, 2013 8:31:26 PM UTC-7, simon place wrote:

    that's basically it, and i did notice most of the cons you mention,
    only... see below for my thinking.
    On Thursday, 21 November 2013 00:56:25 UTC, Kevin Gillette wrote:

    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):
    i think the "automatic" actually solves the main drawbacks, mostly because
    its effectively controlled by the slices capacity parameter.

    benefits:

    - "copying" is avoided

    this is also good because the current level of copying, is
    surprising.(even when not inefficient)
    - less garbage is generated in naive application use cases.

    don't understand 'naive'
    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.

    but, there will always be cases, where copying is massively slower, or
    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.
    - 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.

    true, but you (programmer) know when this can not have happened, and so
    could prevent it when you were exposing implementation externally, (not an
    ideal thing to be doing anyway, experts only?).
    - 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.

    i envisaged array of arrays backing to be numerically very rare and often
    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.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Simon place at Nov 21, 2013 at 10:24 pm
    this would have to be language change, (although non-breaking)
    On Thursday, 21 November 2013 15:10:02 UTC, Caleb Doxsey wrote:

    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.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedNov 20, '13 at 11:32p
activeNov 27, '13 at 3:16a
posts13
users4
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase