When benchmarking in Julia, you always have to remember to do things twice,
so that you are not measuring the JIT compilation time.
(it can also be a good idea to call gc() just before the timings, if there
is significant memory usage).
You also have to be very careful that Julia doesn't simply optimize away
benchmark loops completely (hence the trick with returning the value
from the benchmark function)
I got the following:
*julia> **f1(x) = sizeof(x)<<3 - leading_zeros(x)*
*f1 (generic function with 1 method)*
*julia> **f2(x) = ceil(log2(x))*
*f2 (generic function with 1 method)*
*julia> **f3(x) = length(bin(x))*
*f3 (generic function with 1 method)*
*julia> **function f4(x)*
*n = 0*
*while x != 0*
*n += 1*
*x >>= 1*
*end*
*n*
*end*
*f4 (generic function with 1 method)*
*julia> **ft1(x,n) = (local y ; for i=1:n ; y = f1(x) ; end ; y)*
*ft1 (generic function with 1 method)*
*julia> **ft2(x,n) = (local y ; for i=1:n ; y = f2(x) ; end ; y)*
*ft2 (generic function with 1 method)*
*julia> **ft3(x,n) = (local y ; for i=1:n ; y = f3(x) ; end ; y)*
*ft3 (generic function with 1 method)*
*julia> **ft4(x,n) = (local y ; for i=1:n ; y = f4(x) ; end ; y)*
*ft4 (generic function with 1 method)*
*julia> **@time ft1(x,1000000)*
0.006164 seconds (4 allocations: 160 bytes)
*32*
*julia> **@time ft2(x,1000000)*
0.024435 seconds (1.00 M allocations: 15.259 MB, 8.07% gc time)
*31.0*
*julia> **@time ft3(x,1000000)*
0.070985 seconds (2.00 M allocations: 122.070 MB, 7.80% gc time)
*32*
*julia> **@time ft4(x,1000000)*
0.027962 seconds (4 allocations: 160 bytes)
*3*
On Tuesday, October 6, 2015 at 11:50:19 AM UTC-4, Ravi S wrote:
>
> julia> function nbits(x)
> n = 0
> while x!=0
> n += 1
> x >>= 1
> end;
> return n
> end
> nbits (generic function with 1 method)
>
> julia> @time ceil(log2(x))
> elapsed time: 7.376e-6 seconds (112 bytes allocated)
> 18.0
>
> julia> @time sizeof(x)*8 - leading_zeros(x)
> elapsed time: 9.781e-6 seconds (80 bytes allocated)
> 18
>
> julia> @time length(bin(x))
> elapsed time: 6.693e-6 seconds (176 bytes allocated)
> 18
>
> julia> @time nbits(x)
> elapsed time: 5.425e-6 seconds (80 bytes allocated)
> 18
>
>
> On Tuesday, October 6, 2015 at 9:14:52 PM UTC+5:30, Scott Jones wrote:
>>
>> Well, I asked about how to get it as fast as possible.
>> Turns out, leading_zeros does just what I want, using the lzcnt*
>> instruction :-)
>> If you don't count the unnecessary frame setup (pushq %rbp; movq %rsp,
>> %rbp) and frame pop/return (popq %rbp ; ret), the whole thing I want boils
>> down to 4 instructions, nicely parameterized by Julia on the type ;-)
>>
>>
>> On Tuesday, October 6, 2015 at 11:41:03 AM UTC-4, Tim Holy wrote:
>>>
>>> Presumably, iterating over x>>1 until x == 0 should do the trick?
>>>
>>> --Tim
>>>
>>> On Tuesday, October 06, 2015 08:21:35 AM Scott Jones wrote:
>>> > Sorry! I should have been more specific.
>>> > What I want is:
>>> > 0 -> 0
>>> > 1 -> 1
>>> > 0x8 -> 4
>>> > 0x1f -> 5
>>> > 13 -> 5
>>> >
>>> > i.e. number of bits needed to represent the number.
>>> > I want to pack 2 or 3 values into a unsigned int, (maybe a UInt16, up
>>> to a
>>> > UInt128), that I can then use for sorting purposes efficiently.
>>> > (much more cache efficient, eliminates a bunch of pointer references,
>>> etc.)
>>> >
>>> > Any idea how? (normally, I'd just use the assembly instructions
>>> available
>>> > that do this, but I want to do this in pure Julia [it would be nice if
>>> the
>>> > Julia code
>>> > could actually be smart enough to generate the correct native code ;-)
>>> )
>>> >
>>> > Thanks!
>>> >
>>> > On Tuesday, October 6, 2015 at 11:03:03 AM UTC-4, Steven G. Johnson
>>> wrote:
>>> > > On Tuesday, October 6, 2015 at 10:59:04 AM UTC-4, Scott Jones wrote:
>>> > >> I couldn't find anything yet - is there a recommended / fastest way
>>> to
>>> > >> get the number of bits in a number (I really only need it for
>>> unsigned
>>> > >> values).
>>> > >> Thanks
>>> > >
>>> > > sizeof(number)*8 if you want all the bits (though you'd need to
>>> define a
>>> > > separate method for BigInt), or count_ones(number) if you want the 1
>>> bits.
>>>
>>>
