[Caml-list] Binary logarithm of a power of 2

[Caml-list] Binary logarithm of a power of 2

[Dario Teixeira]

Hi,

In the critical path of an application I need to compute the binary
logarithm of an int32.  With one nuance: I know the input is always
a power of 2, which opens the door to bit-trickery (the log2 of a
power of 2 is simply the position of the sole bit set to '1').

GCC has a builtin function __builtin_ctz which I suppose will translate
into optimal assembly for all platforms, so my current solution uses a
small C stub that basically just invokes this builtin (see below).

Still, my question is whether this is indeed the optimal solution.
Is there some penalty associated with invoking C functions that may
negate the supposed advantage of __builtin_ctz?

Thanks in advance!
Best regards,
Dario Teixeira


external logbin: int32 -> int = "logbin_stub"

CAMLprim value logbin_stub (value v_num)
        {
        CAMLparam1 (v_num);
        CAMLlocal1 (ml_res);

        int32 num = Int32_val (v_num);
        int res = __builtin_ctz (num);

        ml_res = Val_int (res);
        CAMLreturn (ml_res);
        }

Re: [Caml-list] Binary logarithm of a power of 2

[Goswin von Brederlow]

Dario Teixeira <darioteixeira@yahoo.com> writes:

> Hi,
>
> In the critical path of an application I need to compute the binary
> logarithm of an int32.  With one nuance: I know the input is always
> a power of 2, which opens the door to bit-trickery (the log2 of a
> power of 2 is simply the position of the sole bit set to '1').
>
> GCC has a builtin function __builtin_ctz which I suppose will translate
> into optimal assembly for all platforms, so my current solution uses a
> small C stub that basically just invokes this builtin (see below).
>
> Still, my question is whether this is indeed the optimal solution.
> Is there some penalty associated with invoking C functions that may
> negate the supposed advantage of __builtin_ctz?

I doubt you can make an ocaml function that does this faster than
invoking a C function. Esspecially with noalloc that gives you verry
little leeway over the optimized __builtin_ctz. I doubt you can
translate the asm tricks gcc does to ocaml without loosing performance.

> Thanks in advance!
> Best regards,
> Dario Teixeira
>
>
> external logbin: int32 -> int = "logbin_stub"
>
> CAMLprim value logbin_stub (value v_num)
>         {
>         CAMLparam1 (v_num);
>         CAMLlocal1 (ml_res);
>
>         int32 num = Int32_val (v_num);
>         int res = __builtin_ctz (num);
>
>         ml_res = Val_int (res);
>         CAMLreturn (ml_res);
>         }

There are 2 improvements you could make:

1) flag the stub as noalloc and drop the CAML*.
2) add a compiler builtin to the ocaml compiler.

Although the 2nd is probably going to far.

MfG
        Goswin

Re: [Caml-list] Binary logarithm of a power of 2

[Dario Teixeira]

Hi,
 
> Still, my question is whether this is indeed the optimal solution.
> Is there some penalty associated with invoking C functions that may
> negate the supposed advantage of __builtin_ctz?

Thank you, Till and Goswin, for your suggestions.  Marking the stub
as "noalloc" and removing the CAML_ boilerplate did result in a very
noticeable speed up in the synthetic benchmarks I tried.  Great!

Cheers,
Dario

[Caml-list] Re: Binary logarithm of a power of 2

[Sylvain Le Gall]

Hello,

On 27-05-2011, Dario Teixeira <darioteixeira@yahoo.com> wrote:
> Hi,
>  
>> Still, my question is whether this is indeed the optimal solution.
>> Is there some penalty associated with invoking C functions that may
>> negate the supposed advantage of __builtin_ctz?
>
> Thank you, Till and Goswin, for your suggestions.  Marking the stub
> as "noalloc" and removing the CAML_ boilerplate did result in a very
> noticeable speed up in the synthetic benchmarks I tried.  Great!
>

Friday afternoon exercice ;-)

Here is my code:

external logbin: int32 -> int = "logbin_stub" "noalloc"

let logbin_simple i =
  let rec find_bit n =
    if (i lsr n) = 0 then
      n - 1
    else
      find_bit (n + 1)
  in
    if i = 0 then
      0
    else
      find_bit 0

let precomp =
  Array.init
    256
    logbin_simple

let logbin_array i32 =
  let i = Int32.to_int i32 in
  let rec test shift =
    let i =
      0xFF land (i lsr shift)
    in
      match Array.unsafe_get precomp i with
        | 0 ->
            if shift = 0 then
              0
            else
              test (shift - 8)
        | n -> n + shift
  in

  let test32 shift =
    let i =
      Int32.to_int
        (Int32.logand
           0xFFl
           (Int32.shift_right i32 shift))
    in
      match Array.unsafe_get precomp i with
        | 0 ->
            test (shift - 8)
        | n -> n + shift
  in
    if Sys.word_size = 64 then
      test 24
    else
      test32 24

let () =
  List.iter
    (fun i ->
       Printf.printf "logbin_simple %d -> %d\n" i (logbin_simple i);
       Printf.printf "logbin_array  %d -> %d\n" i (logbin_array (Int32.of_int i));
       Printf.printf "logbin        %d -> %d\n" i (logbin (Int32.of_int i));
       Printf.printf "\n\n";
    )
    [ 0; 1; 2; 4; 1024; 2048; 4096; 4194304]


let () =
  Benchmark.tabulate
    (Benchmark.throughputN
       2
       [
         "logbin", (fun () -> logbin 4096l), ();
         "logbin_simple", (fun () -> logbin_simple 4096), ();
         "logbin_array",  (fun () -> logbin_array 4096l), ();
       ])


And the results:

Throughputs for "logbin", "logbin_simple", "logbin_array" each running for at least 2 CPU seconds:
       logbin:  2.14 WALL ( 2.14 usr +  0.00 sys =  2.14 CPU) @ 74191111.86/s (n=158778921)
logbin_simple:  2.02 WALL ( 2.02 usr +  0.00 sys =  2.02 CPU) @ 27884695.31/s (n=56330598)
 logbin_array:  2.05 WALL ( 2.05 usr +  0.00 sys =  2.05 CPU) @ 87426949.77/s (n=179411379)
                    Rate logbin_simple        logbin  logbin_array
logbin_simple 27884695/s            --          -62%          -68%
       logbin 74191112/s          166%            --          -15%
 logbin_array 87426950/s          214%           18%            --


The code is not bug proof, you should check it ;-)

You can except at least 18% increase in term of performance on amd64 and a 1% decrease on i386. 

The 4096 value is not very good for logbin_array because it have to loop more
times, so on greater value, you can expect better performance.

Cheers,
Sylvain Le Gall
-- 
My company: http://www.ocamlcore.com
Linkedin:   http://fr.linkedin.com/in/sylvainlegall
Start an OCaml project here: http://forge.ocamlcore.org
OCaml blogs:                 http://planet.ocamlcore.org

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Xavier Leroy]

On 05/27/2011 03:26 PM, Sylvain Le Gall wrote:

> Friday afternoon exercice ;-)

Same here :-)

> Here is my code:

[ Recursive & array-based implementation in Caml ]

Simpler and maybe faster:

let logbin (n: int32) =
  let n = ref (Int32.add n 0l) and i = ref 0 in
  if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
  if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
  if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
  if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
  if !n >= 0x2l then !i + 1 else !i

Have fun,

- Xavier

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Dario Teixeira]

Hi,

> Simpler and maybe faster:
> 
> let logbin (n: int32) =
>   let n = ref (Int32.add n 0l) and i = ref 0 in
>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>   if !n >= 0x2l then !i + 1 else !i

Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
close to the C-based "noalloc" one (the record holder so far), at least
on an x86_64.

Note that __builtin_ctz actually translates into a single opcode where
available (BSFL in x86_64), and I expect that a modern CPU will do a
decent job with it.  Therefore, despite that a C-based solution will
most likely prevent inlining (right?), it may be hard to beat...

Cheers,
Dario Teixeira

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Till Varoquaux]

And you can probably gain on XL by dropping down to ints and not using refs:

let lb5 n i = if n >= 0x2 then i+1 else i

let lb4 n i =
  if n >= 0x4 then lb5 (n asr 2) (i+2)
  else lb5 n i

let lb3 n i =
  if n >= 0x10 then lb4 (n asr 4) (i+4)
  else lb4 n i

let lb2 n i =
  if n >= 0x100 then lb3 (n asr 8) (i+8)
  else lb3 n i

let logbin n =
  if n >= 0x10000 then lb2 (n asr 16) 16
  else lb2 n 0

(note that you can drop to ints right in logbin itself if you really
need your input to be int32s and you aren't on a 32 bit machine).

This is thoroughly untested.

Till

On Fri, May 27, 2011 at 2:04 PM, Dario Teixeira <darioteixeira@yahoo.com> wrote:
> Hi,
>
>> Simpler and maybe faster:
>>
>> let logbin (n: int32) =
>>   let n = ref (Int32.add n 0l) and i = ref 0 in
>>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>>   if !n >= 0x2l then !i + 1 else !i
>
> Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
> close to the C-based "noalloc" one (the record holder so far), at least
> on an x86_64.
>
> Note that __builtin_ctz actually translates into a single opcode where
> available (BSFL in x86_64), and I expect that a modern CPU will do a
> decent job with it.  Therefore, despite that a C-based solution will
> most likely prevent inlining (right?), it may be hard to beat...
>
> Cheers,
> Dario Teixeira
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Till Varoquaux]

Nevermind. I am actually running slower, bad benchmark.

Shameful,
Till

On Fri, May 27, 2011 at 2:37 PM, Till Varoquaux <till@pps.jussieu.fr> wrote:
> And you can probably gain on XL by dropping down to ints and not using refs:
>
> let lb5 n i = if n >= 0x2 then i+1 else i
>
> let lb4 n i =
>  if n >= 0x4 then lb5 (n asr 2) (i+2)
>  else lb5 n i
>
> let lb3 n i =
>  if n >= 0x10 then lb4 (n asr 4) (i+4)
>  else lb4 n i
>
> let lb2 n i =
>  if n >= 0x100 then lb3 (n asr 8) (i+8)
>  else lb3 n i
>
> let logbin n =
>  if n >= 0x10000 then lb2 (n asr 16) 16
>  else lb2 n 0
>
> (note that you can drop to ints right in logbin itself if you really
> need your input to be int32s and you aren't on a 32 bit machine).
>
> This is thoroughly untested.
>
> Till
>
> On Fri, May 27, 2011 at 2:04 PM, Dario Teixeira <darioteixeira@yahoo.com> wrote:
>> Hi,
>>
>>> Simpler and maybe faster:
>>>
>>> let logbin (n: int32) =
>>>   let n = ref (Int32.add n 0l) and i = ref 0 in
>>>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>>>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>>>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>>>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>>>   if !n >= 0x2l then !i + 1 else !i
>>
>> Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
>> close to the C-based "noalloc" one (the record holder so far), at least
>> on an x86_64.
>>
>> Note that __builtin_ctz actually translates into a single opcode where
>> available (BSFL in x86_64), and I expect that a modern CPU will do a
>> decent job with it.  Therefore, despite that a C-based solution will
>> most likely prevent inlining (right?), it may be hard to beat...
>>
>> Cheers,
>> Dario Teixeira
>>
>>
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa-roc.inria.fr/wws/info/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>

RE: [Caml-list] Re: Binary logarithm of a power of 2

[Harrison, John R]

The following are my pet algorithms for essentially the same problem
of counting leading zeros, and the dual problem of counting trailing
zeros. It should be a routine exercise to translate to OCaml and tweak
the numbers for binary logarithm.

I doubt if these are as fast in practice as some of the other
well-known solutions. However they have the interesting feature that
given infinite parallelism and arranging the sums in a balanced tree,
they can be log(log(N)) + 2 in terms of latencies, rather than the
usual log(N), where N is the number of bits in a word. That is, all
the terms in the sum can be evaluated independently. As such, they
are much more like how the operation might be done in hardware.

// Counting leading zeros in an unsigned 32-bit word
// The "_nz" version will return the wrong answer (31) for zero inputs

#define CLZ32_MASK16 0xFFFF0000ul
#define CLZ32_MASK8  0xFF00FF00ul
#define CLZ32_MASK4  0xF0F0F0F0ul
#define CLZ32_MASK2  0xCCCCCCCCul
#define CLZ32_MASK1  0xAAAAAAAAul

#define clz32_nz(n)                                             \
 (((((n) & CLZ32_MASK16) <= ((n) & ~CLZ32_MASK16)) ? 16 : 0) +  \
  ((((n) & CLZ32_MASK8) <= ((n) & ~CLZ32_MASK8)) ? 8 : 0) +     \
  ((((n) & CLZ32_MASK4) <= ((n) & ~CLZ32_MASK4)) ? 4 : 0) +     \
  ((((n) & CLZ32_MASK2) <= ((n) & ~CLZ32_MASK2)) ? 2 : 0) +     \
  ((((n) & CLZ32_MASK1) <= ((n) & ~CLZ32_MASK1)) ? 1 : 0))

#define clz32(n) (((n)==0) ? 32 : clz32_nz(n))

// Counting trailing zeros in an unsigned 32-bit word
// The ctz32_1bit version is for a single bit

#define ctz32_1bit(n)                                           \
 ((((n) & ~CLZ32_MASK16) ? 0 : 16) +                            \
  (((n) & ~CLZ32_MASK8) ? 0 : 8) +                              \
  (((n) & ~CLZ32_MASK4) ? 0 : 4) +                              \
  (((n) & ~CLZ32_MASK2) ? 0 : 2) +                              \
  (((n) & ~CLZ32_MASK1) ? 0 : 1))

#define ctz32(n) (((n) == 0) ? 32 : ctz32_1bit((n) & -(n)))

John.

-----Original Message-----
From: till.varoquaux@gmail.com [mailto:till.varoquaux@gmail.com] On Behalf Of Till Varoquaux
Sent: Friday, May 27, 2011 11:46 AM
To: Dario Teixeira
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2

Nevermind. I am actually running slower, bad benchmark.

Shameful,
Till

On Fri, May 27, 2011 at 2:37 PM, Till Varoquaux <till@pps.jussieu.fr> wrote:
> And you can probably gain on XL by dropping down to ints and not using refs:
>
> let lb5 n i = if n >= 0x2 then i+1 else i
>
> let lb4 n i =
>  if n >= 0x4 then lb5 (n asr 2) (i+2)
>  else lb5 n i
>
> let lb3 n i =
>  if n >= 0x10 then lb4 (n asr 4) (i+4)
>  else lb4 n i
>
> let lb2 n i =
>  if n >= 0x100 then lb3 (n asr 8) (i+8)
>  else lb3 n i
>
> let logbin n =
>  if n >= 0x10000 then lb2 (n asr 16) 16
>  else lb2 n 0
>
> (note that you can drop to ints right in logbin itself if you really
> need your input to be int32s and you aren't on a 32 bit machine).
>
> This is thoroughly untested.
>
> Till
>
> On Fri, May 27, 2011 at 2:04 PM, Dario Teixeira <darioteixeira@yahoo.com> wrote:
>> Hi,
>>
>>> Simpler and maybe faster:
>>>
>>> let logbin (n: int32) =
>>>   let n = ref (Int32.add n 0l) and i = ref 0 in
>>>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>>>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>>>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>>>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>>>   if !n >= 0x2l then !i + 1 else !i
>>
>> Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
>> close to the C-based "noalloc" one (the record holder so far), at least
>> on an x86_64.
>>
>> Note that __builtin_ctz actually translates into a single opcode where
>> available (BSFL in x86_64), and I expect that a modern CPU will do a
>> decent job with it.  Therefore, despite that a C-based solution will
>> most likely prevent inlining (right?), it may be hard to beat...
>>
>> Cheers,
>> Dario Teixeira
>>
>>
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa-roc.inria.fr/wws/info/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>


-- 
Caml-list mailing list.  Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Richard W.M. Jones]

On Fri, May 27, 2011 at 11:04:16AM -0700, Dario Teixeira wrote:
> Note that __builtin_ctz actually translates into a single opcode where
> available (BSFL in x86_64), and I expect that a modern CPU will do a
> decent job with it.  Therefore, despite that a C-based solution will
> most likely prevent inlining (right?), it may be hard to beat...

It's long been on my OCaml wishlist (along with a 'return' statement)
to be able to use inline asm.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Edgar Friendly]

[-- Attachment #1: Type: text/plain, Size: 678 bytes --]

On 05/28/2011 11:58 AM, Richard W.M. Jones wrote:
> It's long been on my OCaml wishlist (along with a 'return' statement)
> to be able to use inline asm.
Inline asm might not be here, but there's two similar implementations of 
'return', one in Batteries and one in Jane Street Core.

http://ocaml.janestreet.com/?q=node/91
http://ocaml-batteries-team.github.com/batteries-included/hdoc/BatReturn.html

Example (using BatReturn):

|    open Return
    let find_in_array a e =
     label (fun label ->
     for i = 0 to Array.length a - 1 do
       if Array.get a i = e then return label (Some i)
     done;
     None)|


Sharing this in case anyone didn't know about these.

E.

[-- Attachment #2: Type: text/html, Size: 1339 bytes --]

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Matteo Frigo]

A way exists to compute the binary logarithm with one multiplication and
a couple of shifts.  See Charles E. Leiserson, Harald Prokop, and Keith
H. Randall: Using de Bruijn Sequences to Index a 1 in a Computer Word.

The idea is that a magic 64-bit string of zeros and ones exists such
that all possible strings of 6 bits appear as substrings of the string.
Such a sequence is called a "de Bruijn Sequence".  Let K be such a
string interpreted as an int64.  Then K * 2^n shifts K to the left by n
places, leaving a unique encoding of n in the upper 6 bits of the
product.

Knuth Vol. 4A remarks that this is an old trick, invented but not
published by some gentleman at IBM in the late sixties.  (Sorry, I don't
have Knuth at hand for an exact reference.)  However the 1998 paper by
Leiserson et al. should be available via google.

Regards,
Matteo Frigo

Fwd: [Caml-list] Re: Binary logarithm of a power of 2

[Johannes]

A link to the de Bruijn paper can be found on the "Bit Twiddling Hacks" page
linked earlyier in this thread:
http://graphics.stanford.edu/~seander/bithacks.html

I used it myself -- although with JavaScript and did not run any benchmarks --
and I liked the approach, very neat.

2011/5/28 Matteo Frigo <athena@fftw.org>:
> A way exists to compute the binary logarithm with one multiplication and
> a couple of shifts.  See Charles E. Leiserson, Harald Prokop, and Keith
> H. Randall: Using de Bruijn Sequences to Index a 1 in a Computer Word.
>
> The idea is that a magic 64-bit string of zeros and ones exists such
> that all possible strings of 6 bits appear as substrings of the string.
> Such a sequence is called a "de Bruijn Sequence".  Let K be such a
> string interpreted as an int64.  Then K * 2^n shifts K to the left by n
> places, leaving a unique encoding of n in the upper 6 bits of the
> product.
>
> Knuth Vol. 4A remarks that this is an old trick, invented but not
> published by some gentleman at IBM in the late sixties.  (Sorry, I don't
> have Knuth at hand for an exact reference.)  However the 1998 paper by
> Leiserson et al. should be available via google.
>
> Regards,
> Matteo Frigo
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Re: Binary logarithm of a power of 2

[Jean-Christophe Filliâtre]

> Knuth Vol. 4A remarks that this is an old trick, invented but not
> published by some gentleman at IBM in the late sixties.  (Sorry, I don't
> have Knuth at hand for an exact reference.)  However the 1998 paper by
> Leiserson et al. should be available via google.

Another good reference along these lines: Henry Warren's "Hacker's
Delight" (http://www.hackersdelight.org/). My apologies if already
mentioned in this thread.

This book is wonderful and contains many ways to compute the number of
trailing zeros, among other things. (It is cited in volume 4A.)

-- 
Jean-Christophe