FAQ
Hi,

Wouldn't a 'stride' field in slices be a nice feature?
I was wondering this while developing audio code. If slices had stride,
applications wouldn't need to deal with interleaved vs non-interleaved
audio issues.
As for things like reversal, it would be O(1) ( reversed := original[-1:0] )
Inner loops shouldn't be much slower when using a stride. In fact I think
those would keep the same speed in most architectures.

--

Search Discussions

  • Kyle Lemons at Oct 8, 2012 at 11:27 pm

    On Sat, Oct 6, 2012 at 10:58 AM, Jorge Acereda wrote:

    Hi,

    Wouldn't a 'stride' field in slices be a nice feature?
    http://golang.org/doc/go_faq.html#Why_doesnt_Go_have_feature_X

    I was wondering this while developing audio code. If slices had stride,
    applications wouldn't need to deal with interleaved vs non-interleaved
    audio issues.
    Stride complicates a lot of the aspects of slices, including capacity and
    bounds checking, not to mention adding cognitive overhead and making a
    simple index operation potentially have different performance or
    memory/caching implications based on context.

    As for things like reversal, it would be O(1) ( reversed := original[-1:0]
    )
    I don't think it would be quite that simple...

    Inner loops shouldn't be much slower when using a stride. In fact I think
    those would keep the same speed in most architectures.
    conceptually it turns

    type slice struct {
    data []type
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    into

    type slice struct {
    data []type
    start int
    stride int
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    idx := s.start + i * s.stride
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    While some amount of that complexity is covered under assembly
    instructions, it makes the slice type larger to store in memory and there
    are *two* stride computations -- one for the "slice" stride before bounds
    checking and one for the actual size of the data type.

    --
  • Sebastien Binet at Oct 9, 2012 at 7:30 am

    Kyle Lemons writes:
    On Sat, Oct 6, 2012 at 10:58 AM, Jorge Acereda wrote:

    Hi,

    Wouldn't a 'stride' field in slices be a nice feature?
    http://golang.org/doc/go_faq.html#Why_doesnt_Go_have_feature_X

    I was wondering this while developing audio code. If slices had stride,
    applications wouldn't need to deal with interleaved vs non-interleaved
    audio issues.
    Stride complicates a lot of the aspects of slices, including capacity and
    bounds checking, not to mention adding cognitive overhead and making a
    simple index operation potentially have different performance or
    memory/caching implications based on context.

    As for things like reversal, it would be O(1) ( reversed := original[-1:0]
    )
    I don't think it would be quite that simple...

    Inner loops shouldn't be much slower when using a stride. In fact I think
    those would keep the same speed in most architectures.
    conceptually it turns

    type slice struct {
    data []type
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    into

    type slice struct {
    data []type
    start int
    stride int
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    idx := s.start + i * s.stride
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    While some amount of that complexity is covered under assembly
    instructions, it makes the slice type larger to store in memory and there
    are *two* stride computations -- one for the "slice" stride before bounds
    checking and one for the actual size of the data type.
    probably shoving all this overhead into the current slice type is too
    much for the common case, but having strided slices and n-dim slices
    would be really great to solve a whole class of problems (audio & image
    processing, linear algebra, particle physics, ...)

    just look at how numpy is used in the python world.

    (not willing to bring that discussion again, but having generics would
    allow to easily write that n-dim strided slice, short of having a
    convenient way to index it)

    -s
  • Jorge Acereda at Oct 9, 2012 at 8:00 pm

    On Oct 9, 2012, at 12:59 AM, Kyle Lemons wrote:

    On Sat, Oct 6, 2012 at 10:58 AM, Jorge Acereda <jacereda@gmail.com> wrote
    As for things like reversal, it would be O(1) ( reversed := original[-1:0] )
    I don't think it would be quite that simple...
    I'm not sure I like the idea of making slices circular, we could use this instead:

    reversed := original[len(original)-1:-1]

    The original code:

    void
    runtime·sliceslice(Slice old, uint64 lb, uint64 hb, uint64 width, Slice ret)
    {
    ...
    ret.len = hb - lb;
    ret.cap = old.cap - lb;
    ret.array = old.array + lb*width;
    ...
    }

    Would become: (the width of the type would be premultiplied in the stride field, no need to pass the width).

    void
    runtime·sliceslice(Slice old, uint64 lb, uint64 hb, int stride, Slice ret)
    {
    ...
    if (hb >= lb) {
    ret.len = hb - lb;
    ret.cap = (old.cap - lb) / stride;
    ret.stride = old.stride * stride;
    } else {
    ret.len = lb - hb;
    ret.cap = ret.len / stride;
    ret.stride = - old.stride * stride;
    }
    ret.array = old.array + lb * old.stride;
    ...
    }

    And there you have O(1) reversal. Also:

    evens := original[0::2]
    odds := original[1::2]


    Inner loops shouldn't be much slower when using a stride. In fact I think those would keep the same speed in most architectures.

    conceptually it turns

    type slice struct {
    data []type
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    into

    type slice struct {
    data []type
    start int
    stride int
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    idx := s.start + i * s.stride
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    While some amount of that complexity is covered under assembly instructions, it makes the slice type larger to store in memory and there are *two* stride computations -- one for the "slice" stride before bounds checking and one for the actual size of the data type.

    It's not as bad as you paint it, just premultiply the type size by the desired stride. Also, the 'start' field is not necessary AFAICS:

    type slice struct {
    data []byte
    len int
    cap int
    stride int
    }

    func (s slice) ref(i int) type {
    if uint(i) >= s.len { panic }
    return *(type*)(s.data + i * s.stride)
    }

    In your code there's an implicit multiplication also by the size of the type. It's true that in my code the multiplication is less optimizable and will probably be a real MUL (although there could be fast paths).

    Things like copy() wouldn't need the multiplication.

    --
  • Kyle Lemons at Oct 9, 2012 at 9:20 pm
    On Tue, Oct 9, 2012 at 1:00 PM, Jorge Acereda wrote:
    On Oct 9, 2012, at 12:59 AM, Kyle Lemons wrote:

    On Sat, Oct 6, 2012 at 10:58 AM, Jorge Acereda <jacereda@gmail.com>
    wrote
    As for things like reversal, it would be O(1) ( reversed :=
    original[-1:0] )
    I don't think it would be quite that simple...
    I'm not sure I like the idea of making slices circular, we could use this
    instead:

    reversed := original[len(original)-1:-1]

    The original code:

    void
    runtime·sliceslice(Slice old, uint64 lb, uint64 hb, uint64 width, Slice
    ret)
    {
    ...
    ret.len = hb - lb;
    ret.cap = old.cap - lb;
    ret.array = old.array + lb*width;
    ...
    }

    Would become: (the width of the type would be premultiplied in the stride
    field, no need to pass the width).

    void
    runtime·sliceslice(Slice old, uint64 lb, uint64 hb, int stride, Slice ret)
    {
    ...
    if (hb >= lb) {
    ret.len = hb - lb;
    ret.cap = (old.cap - lb) / stride;
    ret.stride = old.stride * stride;
    } else {
    ret.len = lb - hb;
    ret.cap = ret.len / stride;
    ret.stride = - old.stride * stride;
    }
    ret.array = old.array + lb * old.stride;
    ...
    }

    And there you have O(1) reversal. Also:

    evens := original[0::2]
    odds := original[1::2]

    There would be much more sweeping changes than just sliceslice. Also,
    start is required if you want slice reversal unless you want it to always
    start at end if stride is negative, but that puts another conditional in
    every index operation that might be mis-guessed by the branch predictor.

    Inner loops shouldn't be much slower when using a stride. In fact I
    think those would keep the same speed in most architectures.
    conceptually it turns

    type slice struct {
    data []type
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    into

    type slice struct {
    data []type
    start int
    stride int
    len int
    cap int
    }

    func (s slice) ref(i int) type {
    idx := s.start + i * s.stride
    if i < 0 || i > s.len { panic }
    return s.data[i]
    }

    While some amount of that complexity is covered under assembly
    instructions, it makes the slice type larger to store in memory and there
    are *two* stride computations -- one for the "slice" stride before bounds
    checking and one for the actual size of the data type.


    It's not as bad as you paint it, just premultiply the type size by the
    desired stride. Also, the 'start' field is not necessary AFAICS:

    type slice struct {
    data []byte
    len int
    cap int
    stride int
    }

    func (s slice) ref(i int) type {
    if uint(i) >= s.len { panic }
    return *(type*)(s.data + i * s.stride)
    }

    In your code there's an implicit multiplication also by the size of the
    type. It's true that in my code the multiplication is less optimizable and
    will probably be a real MUL (although there could be fast paths).

    Things like copy() wouldn't need the multiplication.
    --
  • Jorge Acereda at Oct 9, 2012 at 10:35 pm

    On Oct 9, 2012, at 10:25 PM, Kyle Lemons wrote:

    There would be much more sweeping changes than just sliceslice. Also, start is required if you want slice reversal unless you want it to always start at end if stride is negative, but that puts another conditional in every index operation that might be mis-guessed by the branch predictor.
    Of course there would be more changes, but not that many. But there's also a lot to gain (flexibility and, more important, less memory copying...). It's just a matter of putting those in a scale.

    I still can't see what 'start' is all about. If I have:

    original := []int{0,1,2,3}

    reversed := original[3:-1]

    reversed would look like this:

    data points to the element '3'
    len is 4
    cap is 4
    stride is -sizeof(int)

    And index operations wouldn't require any conditional. reversed[1] would just return

    *(int*)(data + 1 * stride)

    yielding element 2.

    Am I missing something?

    --
  • Bryanturley at Oct 9, 2012 at 9:08 pm
    I would like to introduce you guys to my friend and constant coding
    companion
    http://en.wikipedia.org/wiki/KISS_principle

    Your welcome for fixing what must be piles of strange code.

    --
  • Jorge Acereda at Oct 9, 2012 at 9:14 pm

    On Oct 9, 2012, at 11:00 PM, bryanturley wrote:

    I would like to introduce you guys to my friend and constant coding companion
    http://en.wikipedia.org/wiki/KISS_principle
    In what way do you consider this:

    l := len(original)/2
    evens := make([]int, l)
    for i = 0; i < l; i++ {
    evens[i] = original[2*i]
    }

    Simpler than this?

    evens := original[0::2]

    The complexity is there, it's just a matter of putting it in the language or putting it in the hands of the programmer.
    And computationally, the second option is simpler.

    Your welcome for fixing what must be piles of strange code.


    --
    --
  • Dan Kortschak at Oct 9, 2012 at 11:05 pm
    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.

    It's lexically simpler when only the go code is simpler.
    On 10/10/2012, at 7:44 AM, "Jorge Acereda" wrote:

    evens := original[0::2]

    The complexity is there, it's just a matter of putting it in the language or putting it in the hands of the programmer.
    And computationally, the second option is simpler.
    --
  • Dan Kortschak at Oct 9, 2012 at 9:30 pm
    s/go code is simpler/go code is considered/
    On 10/10/2012, at 7:59 AM, "Dan Kortschak" wrote:

    It's lexically simpler when only the go code is simpler.
    --
  • Jorge Acereda at Oct 9, 2012 at 9:44 pm

    On Oct 9, 2012, at 11:28 PM, Dan Kortschak wrote:

    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.
    No need to iterate over the elements. Slicing doesn't iterate. So, we are talking here of O(N) in the first case and O(1) in the second. According to my book, the second option is computationally simpler.
    And the fact is that all range loops in existence already consider that the step is not 1when the type width isn't 1.
    It's lexically simpler when only the go code is simpler.
    On 10/10/2012, at 7:44 AM, "Jorge Acereda" wrote:

    evens := original[0::2]

    The complexity is there, it's just a matter of putting it in the language or putting it in the hands of the programmer.
    And computationally, the second option is simpler.
    --
  • Dan Kortschak at Oct 9, 2012 at 10:33 pm
    In the assignment there you copy all the stride an start location fields as well as the fields that already exist in slices as they exist. The is extra overhead. When you do actually range on a slice, the costs are there - for all slice uses, even those that do not have a need for non unity striding.
    On 10/10/2012, at 8:06 AM, "Jorge Acereda" wrote:

    On Oct 9, 2012, at 11:28 PM, Dan Kortschak wrote:

    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.
    No need to iterate over the elements. Slicing doesn't iterate. So, we are talking here of O(N) in the first case and O(1) in the second. According to my book, the second option is computationally simpler.
    And the fact is that all range loops in existence already consider that the step is not 1when the type width isn't 1.
    It's lexically simpler when only the go code is simpler.
    On 10/10/2012, at 7:44 AM, "Jorge Acereda" wrote:

    evens := original[0::2]

    The complexity is there, it's just a matter of putting it in the language or putting it in the hands of the programmer.
    And computationally, the second option is simpler.
    --
    --
  • Rémy Oudompheng at Oct 9, 2012 at 10:41 pm

    On 2012/10/9 Jorge Acereda wrote:
    On Oct 9, 2012, at 11:28 PM, Dan Kortschak wrote:

    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.
    No need to iterate over the elements. Slicing doesn't iterate. So, we are talking here of O(N) in the first case and O(1) in the second. According to my book, the second option is computationally simpler.
    And the fact is that all range loops in existence already consider that the step is not 1when the type width isn't 1.
    It's true but having a stride in slices could hide the fact that we
    stop using a contiguous block of memory, which can be quite important,
    and goes a bit against explicitness.

    Rémy.
    It's lexically simpler when only the go code is simpler.
    On 10/10/2012, at 7:44 AM, "Jorge Acereda" wrote:

    evens := original[0::2]

    The complexity is there, it's just a matter of putting it in the language or putting it in the hands of the programmer.
    And computationally, the second option is simpler.
    --
    --
  • Jorge Acereda at Oct 9, 2012 at 11:22 pm

    On Oct 9, 2012, at 11:39 PM, Rémy Oudompheng wrote:
    On 2012/10/9 Jorge Acereda wrote:
    On Oct 9, 2012, at 11:28 PM, Dan Kortschak wrote:

    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.
    No need to iterate over the elements. Slicing doesn't iterate. So, we are talking here of O(N) in the first case and O(1) in the second. According to my book, the second option is computationally simpler.
    And the fact is that all range loops in existence already consider that the step is not 1when the type width isn't 1.
    It's true but having a stride in slices could hide the fact that we
    stop using a contiguous block of memory, which can be quite important,
    and goes a bit against explicitness.
    Ok, you bring what I consider the first compelling argument. Things like bindings to external libraries would need to perform something like:

    argumentToExternalLibrary := flatten(stridedSlice)

    flatten() would return the original slice for plain slices and perform a copy for strided slices.

    As for things like cache issues, the alternative (copying) isn't much better.

    --
  • Bryanturley at Oct 9, 2012 at 10:08 pm

    On Tuesday, October 9, 2012 4:29:02 PM UTC-5, kortschak wrote:
    How is this computationally simpler? You still need, at some level, to
    iterate over the section of memory with increments of 2, just as is the
    case in the explicit go code, but now every range loop in existence needs
    to consider that the range step may not be 1.
    Was about to say something almost exactly like this. Adding checks to
    every slice operation for stride would make all non strided slices
    needlessly slower.
    Perhaps i += 2 in your for loop?

    Also don't make a new slice for data your just going to parse that is
    inefficient...


    --
  • Bryanturley at Oct 9, 2012 at 9:43 pm

    Also don't make a new slice for data your just going to parse that is
    inefficient...
    Should have read make() not make ;)
    Making a new slice by slicing a chunk off is not inefficient.
    x := y[2:6]

    --
  • Jorge Acereda at Oct 9, 2012 at 11:02 pm

    On Oct 9, 2012, at 11:39 PM, bryanturley wrote:

    On Tuesday, October 9, 2012 4:29:02 PM UTC-5, kortschak wrote:
    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.


    Was about to say something almost exactly like this. Adding checks to every slice operation for stride would make all non strided slices needlessly slower.
    Only by a marginal amount. And that kind of things can be heavily optimized as the compiler evolves. Explicit code can't.

    Perhaps i += 2 in your for loop?

    Also don't make a new slice for data your just going to parse that is inefficient...
    What do you mean? That I can extract the even elements just by skipping by 2 instead of creating a new slice? Of course, but the same applies to:

    half := original[0:len(original)/2]

    You could just change a loop limit instead of creating a new slice, but as soon as you need to pass that to a function you'll also need to pass the limit and that's not the Go way.

    --
  • Dan Kortschak at Oct 9, 2012 at 10:08 pm

    On 10/10/2012, at 8:25 AM, "Jorge Acereda" wrote:

    On Oct 9, 2012, at 11:39 PM, bryanturley wrote:

    On Tuesday, October 9, 2012 4:29:02 PM UTC-5, kortschak wrote:
    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.


    Was about to say something almost exactly like this. Adding checks to every slice operation for stride would make all non strided slices needlessly slower.
    Only by a marginal amount. And that kind of things can be heavily optimized as the compiler evolves. Explicit code can't.
    Why can't it?
    Perhaps i += 2 in your for loop?

    Also don't make a new slice for data your just going to parse that is inefficient...
    What do you mean? That I can extract the even elements just by skipping by 2 instead of creating a new slice? Of course, but the same applies to:

    half := original[0:len(original)/2]

    You could just change a loop limit instead of creating a new slice, but as soon as you need to pass that to a function you'll also need to pass the limit and that's not the Go way.
    The 'Go way' would be to make a new type StridedSlice struct { Data []T; Stride, Start int } with an appropriate Range method.

    --
  • Dan Kortschak at Oct 9, 2012 at 10:13 pm
    Or without a Range method.
    On 10/10/2012, at 8:38 AM, "Dan Kortschak" wrote:

    The 'Go way' would be to make a new type StridedSlice struct { Data []T; Stride, Start int } with an appropriate Range method.
    --
  • Jorge Acereda at Oct 9, 2012 at 11:15 pm

    On Oct 10, 2012, at 12:08 AM, Dan Kortschak wrote:


    On 10/10/2012, at 8:25 AM, "Jorge Acereda" wrote:

    On Oct 9, 2012, at 11:39 PM, bryanturley wrote:

    On Tuesday, October 9, 2012 4:29:02 PM UTC-5, kortschak wrote:
    How is this computationally simpler? You still need, at some level, to iterate over the section of memory with increments of 2, just as is the case in the explicit go code, but now every range loop in existence needs to consider that the range step may not be 1.


    Was about to say something almost exactly like this. Adding checks to every slice operation for stride would make all non strided slices needlessly slower.
    Only by a marginal amount. And that kind of things can be heavily optimized as the compiler evolves. Explicit code can't.
    Why can't it?
    The compiler can get smarter, but probably not so smart as to remove the explicit copy you're telling it to perform.
    Perhaps i += 2 in your for loop?

    Also don't make a new slice for data your just going to parse that is inefficient...
    What do you mean? That I can extract the even elements just by skipping by 2 instead of creating a new slice? Of course, but the same applies to:

    half := original[0:len(original)/2]

    You could just change a loop limit instead of creating a new slice, but as soon as you need to pass that to a function you'll also need to pass the limit and that's not the Go way.
    The 'Go way' would be to make a new type StridedSlice struct { Data []T; Stride, Start int } with an appropriate Range method.
    Looks like we're entering the 'generics' war here...

    --
  • Dan Kortschak at Oct 9, 2012 at 10:53 pm
    There are two use cases, one where you are actually making a copy for later use in which case the computation expense is approximately the same in long run, or you are ranging over the slice and so you don't need any copy and the computational expense is again approximately the same. So we have no significant performance benefit in this special case in return for increased language complexity and computation cost for the common case.
    On 10/10/2012, at 8:47 AM, "Jorge Acereda" wrote:

    The compiler can get smarter, but probably not so smart as to remove the explicit copy you're telling it to perform.
    --
  • Bryanturley at Oct 10, 2012 at 12:06 am

    On Tuesday, October 9, 2012 4:00:08 PM UTC-5, bryanturley wrote:
    I would like to introduce you guys to my friend and constant coding
    companion
    http://en.wikipedia.org/wiki/KISS_principle

    Your welcome for fixing what must be piles of strange code.

    Prob should have linked you here as well, different name same concept
    written by one of the core go authors
    http://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html
    <--


    --

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedOct 6, '12 at 5:58p
activeOct 10, '12 at 12:06a
posts22
users6
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase