FAQ
Hi gophers,

I am working on a integer compression package and was hoping I can get some help on optimizing a specific function.
func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
var mask uint32
mask |= (i[pos] - initoffset)

for k := pos + 1; k < pos + length; k++ {
mask |= i[k] - i[k - 1]
}

return NumberOfBitsUint32(mask)
}
According to pprof, my program spends 65% of the time in this function. Most of that time is probably in the for loop. Basically this function takes an array of integers, calculate the delta between current and previous integer, OR with the mask, and finally determine the number of bits in the final mask.

Total: 237 samples
      151 63.7% 63.7% 151 63.7% github.com/reducedb/encoding.MaxDiffBits
       74 31.2% 94.9% 74 31.2% runtime.memclr

I was wondering if anyone has any suggestions on how I might be able to optimize this further. Pls let me know if I am not asking the right question.

Thanks for your help in advance!

Jian

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

  • Ian Lance Taylor at Oct 4, 2013 at 5:13 pm

    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:
    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

         last := i[pos]
         for k := pos + 1; k < pos + length; k++ {
             here := i[k]
             mask |= here - last
             last = here
         }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

         last := i[pos]
         for _, here := range i[pos+1:pos+length] {
             mask |= here - last
             last = here
         }

    Ian

    --
    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.
  • Donovan Hide at Oct 4, 2013 at 5:22 pm
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int) uint32
    {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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.
  • Rodrigo Kochenburger at Oct 4, 2013 at 5:42 pm
    Not that will impact performance but you could use slicing here instead of
    passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK

    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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.
    --
    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.
  • Jian Zhen at Oct 4, 2013 at 6:03 pm
    Thanks Rodrigo. I agree and will fix.
    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger wrote:

    Not that will impact performance but you could use slicing here instead of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints, pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK


    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int) uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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.
    --
    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.
  • Michael Jones at Oct 4, 2013 at 6:46 pm
    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
      /*
    // iterative version is clear
      var count uint64
    for word := n; word != 0; word >>= 1 {
      count += word & 1
    }
      return int(count)
    */

    // direct version is fast
    word := n
      word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
      return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.

    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:

    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger wrote:

    Not that will impact performance but you could use slicing here instead of
    passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK

    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

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

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


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

    --
    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.
  • Rodrigo Kochenburger at Oct 4, 2013 at 6:53 pm
    Btw, the 32 bit version would be:

    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

    - RK

    On Fri, Oct 4, 2013 at 11:45 AM, Michael Jones wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.

    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:

    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger <divoxx@gmail.com>
    wrote:

    Not that will impact performance but you could use slicing here instead
    of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK

    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

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

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


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765
    --
    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.
  • Jian Zhen at Oct 4, 2013 at 8:23 pm
    Michael, Rodrigo,

    Thanks for this. I have to admit that the NumberOfBitsUnit32 is actually misnamed. It's actually not counting the number of bits in a uint32. It's finding the position of the most significant bit. I will rename the function. You can find that function here:
    https://github.com/reducedb/encoding/blob/master/util.go#L65

    It, fortunately, is not a bottleneck in my profiling, afaict.

    For pop count, I use the same function you described below here: https://github.com/reducedb/bitmap/blob/master/ewah/bitcounter.go#L69

    Definitely a fast one!

    thanks

    Jian
    On Oct 4, 2013, at 11:45 AM, Michael Jones wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.


    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:
    Thanks Rodrigo. I agree and will fix.
    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger wrote:

    Not that will impact performance but you could use slicing here instead of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints, pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK


    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int) uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

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

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



    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1 650-335-5765
    --
    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.
  • Dga at Oct 5, 2013 at 1:00 am
    Hi, Jian - if you _do_ need an optimized version of find first set, you
    might steal it from:

    go/src/pkg/math/big/arith_{platform}.s
    as the function bitLen, at the end of the file.

    I keep meaning to make a coherent proposal to split out the bit
    manipulation functions into their own pkg or as language intrinsics, but
    maybe someone will beat me to it some day. :-)

       -Dave
    On Friday, October 4, 2013 4:23:03 PM UTC-4, Jian Zhen wrote:

    Michael, Rodrigo,

    Thanks for this. I have to admit that the NumberOfBitsUnit32 is actually
    misnamed. It's actually not counting the number of bits in a uint32. It's
    finding the position of the most significant bit. I will rename the
    function. You can find that function here:
    https://github.com/reducedb/encoding/blob/master/util.go#L65

    It, fortunately, is not a bottleneck in my profiling, afaict.

    For pop count, I use the same function you described below here:
    https://github.com/reducedb/bitmap/blob/master/ewah/bitcounter.go#L69

    Definitely a fast one!

    thanks

    Jian

    On Oct 4, 2013, at 11:45 AM, Michael Jones <m...@google.com <javascript:>>
    wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.


    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen <zhe...@gmail.com <javascript:>
    wrote:
    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger <div...@gmail.com<javascript:>>
    wrote:

    Not that will impact performance but you could use slicing here instead
    of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK


    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide <donov...@gmail.com<javascript:>
    wrote:
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor <ia...@golang.org<javascript:>
    wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen <zhe...@gmail.com<javascript:>>
    wrote:
    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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...@googlegroups.com <javascript:>.
    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...@googlegroups.com <javascript:>.
    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...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    Michael T. Jones | Chief Technology Advocate | m...@google.com<javascript:>
    +1 650-335-5765
    --
    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.
  • Jian Zhen at Oct 5, 2013 at 5:43 am
    Thanks Dave.

    That looks interesting and may definitely come in handy at some point. The nlz (number of leading zeros) function seems pretty efficient and it's not a bottleneck so I may just stick with it for now. Appreciate the pointer though.

    The MaxDiffBits loop still shows up 50% of the time but I am not sure I know what else to do to optimize that. With the changes I made it should be "good enough" for now though.

    Jian
    On Oct 4, 2013, at 6:00 PM, dga wrote:

    Hi, Jian - if you _do_ need an optimized version of find first set, you might steal it from:

    go/src/pkg/math/big/arith_{platform}.s
    as the function bitLen, at the end of the file.

    I keep meaning to make a coherent proposal to split out the bit manipulation functions into their own pkg or as language intrinsics, but maybe someone will beat me to it some day. :-)

    -Dave

    On Friday, October 4, 2013 4:23:03 PM UTC-4, Jian Zhen wrote:
    Michael, Rodrigo,

    Thanks for this. I have to admit that the NumberOfBitsUnit32 is actually misnamed. It's actually not counting the number of bits in a uint32. It's finding the position of the most significant bit. I will rename the function. You can find that function here:
    https://github.com/reducedb/encoding/blob/master/util.go#L65

    It, fortunately, is not a bottleneck in my profiling, afaict.

    For pop count, I use the same function you described below here: https://github.com/reducedb/bitmap/blob/master/ewah/bitcounter.go#L69

    Definitely a fast one!

    thanks

    Jian
    On Oct 4, 2013, at 11:45 AM, Michael Jones wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.


    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:
    Thanks Rodrigo. I agree and will fix.
    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger wrote:

    Not that will impact performance but you could use slicing here instead of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints, pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK


    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int) uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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...@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...@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...@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.



    --
    Michael T. Jones | Chief Technology Advocate | m...@google.com | +1 650-335-5765

    --
    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.
  • Alexei Sholik at Oct 5, 2013 at 6:46 am
    Nice trick, Michael. There is another clear way to write the iterative
    version that will have less iterations for a "sparse" number:

    var count uint64
      for word := n; word != 0; word &= word-1 {
    count++
    }
      return int(count)

    It's called Kernighan's way to count set bits.
    http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

    On Fri, Oct 4, 2013 at 9:45 PM, Michael Jones wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.

    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:

    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger <divoxx@gmail.com>
    wrote:

    Not that will impact performance but you could use slicing here instead
    of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK

    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

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

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


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

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


    --
    Best regards
    Alexei Sholik

    --
    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.
  • Michael Jones at Oct 5, 2013 at 3:48 pm
    Yes, good!

    On Fri, Oct 4, 2013 at 11:46 PM, Alexei Sholik wrote:

    Nice trick, Michael. There is another clear way to write the iterative
    version that will have less iterations for a "sparse" number:

    var count uint64
    for word := n; word != 0; word &= word-1 {
    count++
    }
    return int(count)

    It's called Kernighan's way to count set bits.
    http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

    On Fri, Oct 4, 2013 at 9:45 PM, Michael Jones wrote:

    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.

    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen wrote:

    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger <divoxx@gmail.com>
    wrote:

    Not that will impact performance but you could use slicing here instead
    of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK

    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

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

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


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

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


    --
    Best regards
    Alexei Sholik


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

    --
    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.
  • Travis at Oct 7, 2013 at 2:13 am
    If I'm reading this right and you're computing essentially the hamming
    distance between two integers, why not use a lookup table to make it a
    guaranteed 4 operations per integer akin
    to https://github.com/twmb/hamming/blob/master/hamming.go ?
    On Saturday, October 5, 2013 10:48:10 AM UTC-5, Michael Jones wrote:

    Yes, good!


    On Fri, Oct 4, 2013 at 11:46 PM, Alexei Sholik <alcos...@gmail.com<javascript:>
    wrote:
    Nice trick, Michael. There is another clear way to write the iterative
    version that will have less iterations for a "sparse" number:

    var count uint64
    for word := n; word != 0; word &= word-1 {
    count++
    }
    return int(count)

    It's called Kernighan's way to count set bits.
    http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan


    On Fri, Oct 4, 2013 at 9:45 PM, Michael Jones <m...@google.com<javascript:>
    wrote:
    One other comment. Is NumberOfBitsUint32(mask) fast?

    My 64 bit version is fast...

    func CountOnesUint64(n uint64) int {
    /*
    // iterative version is clear
    var count uint64
    for word := n; word != 0; word >>= 1 {
    count += word & 1
    }
    return int(count)
    */

    // direct version is fast
    word := n
    word -= (word >> 1) & 0x5555555555555555
    word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
    return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) *
    0x101010101010101) >> 56)
    }

    and a 32-bit version would be faster.


    On Fri, Oct 4, 2013 at 11:03 AM, Jian Zhen <zhe...@gmail.com<javascript:>
    wrote:
    Thanks Rodrigo. I agree and will fix.

    On Oct 4, 2013, at 10:42 AM, Rodrigo Kochenburger <div...@gmail.com<javascript:>>
    wrote:

    Not that will impact performance but you could use slicing here instead
    of passing pos and length:

    func MaxDiffBits2(initoffset uint32, ints []uint32) uint32 {
    mask := ints[0] - initoffset
    last := ints[0]
    for _, v := range ints[1:] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }

    And then when you call, instead of doing MaxDiffBits2(initoffset, ints,
    pos, len) you do MaxDiffBits2(intoffset, ints[pos:pos+len]).

    - RK


    On Fri, Oct 4, 2013 at 10:22 AM, Donovan Hide <donov...@gmail.com<javascript:>
    wrote:
    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int)
    uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor <ia...@golang.org<javascript:>
    wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen <zhe...@gmail.com<javascript:>>
    wrote:
    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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...@googlegroups.com <javascript:>.
    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...@googlegroups.com <javascript:>.
    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...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    Michael T. Jones | Chief Technology Advocate | m...@google.com<javascript:>
    +1 650-335-5765
    --
    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...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    Best regards
    Alexei Sholik


    --
    Michael T. Jones | Chief Technology Advocate | m...@google.com<javascript:>
    +1 650-335-5765
    --
    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.
  • Jian Zhen at Oct 4, 2013 at 6:02 pm
    Ian, Donovan,

    Really appreciate your help!

    I tried 3 versions. First is my original. Second is is the first one that Ian suggested. Third uses range instead of for loop.

    Here are my results. Definitely noticeable improvement.

    Third
    -----
    Compressed 144285498 integers in 320398464 ns
           15 50.0% 50.0% 18 60.0% github.com/reducedb/encoding.MaxDiffBits3

    Second
    -----
    Compressed 144285498 integers in 373342544 ns
           17 47.2% 47.2% 21 58.3% github.com/reducedb/encoding.MaxDiffBits2

    First
    -----
    Compressed 144285498 integers in 423461957 ns
           25 62.5% 62.5% 29 72.5% github.com/reducedb/encoding.MaxDiffBits1

    Thanks!

    Jian
    On Oct 4, 2013, at 10:22 AM, Donovan Hide wrote:

    Beat me to it!

    func MaxDiffBits2(initoffset uint32, ints []uint32, pos, length int) uint32 {
    mask := ints[pos] - initoffset
    last := ints[pos]
    for _, v := range ints[pos+1 : pos+length] {
    mask |= v - last
    last = v
    }
    return NumberOfBitsUint32(mask)
    }


    On 4 October 2013 18:13, Ian Lance Taylor wrote:
    On Fri, Oct 4, 2013 at 10:03 AM, Jian Zhen wrote:

    I am working on a integer compression package and was hoping I can get some
    help on optimizing a specific function.

    func MaxDiffBits(initoffset uint32, i []uint32, pos, length int) uint32 {
    var mask uint32
    mask |= (i[pos] - initoffset)

    for k := pos + 1; k < pos + length; k++ {
    mask |= i[k] - i[k - 1]
    }

    return NumberOfBitsUint32(mask)
    }
    One thing that jumps to mind is that every time you index into a slice
    the compiler is doing a bounds check. So you can eliminate some
    bounds checks by writing this as

    last := i[pos]
    for k := pos + 1; k < pos + length; k++ {
    here := i[k]
    mask |= here - last
    last = here
    }

    The next thing to consider is that a range loop eliminates even more
    bounds checks, so try something along the lines of

    last := i[pos]
    for _, here := range i[pos+1:pos+length] {
    mask |= here - last
    last = here
    }

    Ian

    --
    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.
  • RickyS at Oct 7, 2013 at 7:54 am
    More about population counts here:
    http://dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html

    Includes a reference to Hakmem.

    See also Hackers Delight <http://www.hackersdelight.org/>. There is a nice
    list of links at the bottom.



    --
    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
postedOct 4, '13 at 5:03p
activeOct 7, '13 at 7:54a
posts15
users9
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase