* highest bit, statically determined
@ 2012-09-29 17:34 Georg Bauhaus
2012-09-29 18:11 ` Pascal Obry
` (2 more replies)
0 siblings, 3 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-09-29 17:34 UTC (permalink / raw)
Is there a shorter/better way of having the compiler
find the highest bit = 1 in a static numeric constant?
If N is such a constant, e.g. Some_Type'Last where
Some_Type'Size = 8 and its bound are static, then
Highest_Bit_In_Octet : constant :=
Natural'Max
(8 * Boolean'Pos (N / 2**7 > 0),
Natural'Max
(7 * Boolean'Pos (N / 2**6 > 0),
Natural'Max
(6 * Boolean'Pos (N / 2**5 > 0),
Natural'Max
(5 * Boolean'Pos (N / 2**4 > 0),
Natural'Max
(4 * Boolean'Pos (N / 2**3 > 0),
Natural'Max
(3 * Boolean'Pos (N / 2**2 > 0),
Natural'Max
(2 * Boolean'Pos (N / 2**1 > 0),
Natural'Max
(1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 17:34 highest bit, statically determined Georg Bauhaus
@ 2012-09-29 18:11 ` Pascal Obry
2012-09-29 18:59 ` Georg Bauhaus
2012-09-29 18:57 ` Bill Findlay
2012-09-30 15:39 ` Anatoly Chernyshev
2 siblings, 1 reply; 28+ messages in thread
From: Pascal Obry @ 2012-09-29 18:11 UTC (permalink / raw)
To: Georg Bauhaus
Georg,
> Is there a shorter/better way of having the compiler
> find the highest bit = 1 in a static numeric constant?
>
> If N is such a constant, e.g. Some_Type'Last where
> Some_Type'Size = 8 and its bound are static, then
>
> Highest_Bit_In_Octet : constant :=
> Natural'Max
> (8 * Boolean'Pos (N / 2**7 > 0),
> Natural'Max
> (7 * Boolean'Pos (N / 2**6 > 0),
> Natural'Max
> (6 * Boolean'Pos (N / 2**5 > 0),
> Natural'Max
> (5 * Boolean'Pos (N / 2**4 > 0),
> Natural'Max
> (4 * Boolean'Pos (N / 2**3 > 0),
> Natural'Max
> (3 * Boolean'Pos (N / 2**2 > 0),
> Natural'Max
> (2 * Boolean'Pos (N / 2**1 > 0),
> Natural'Max
> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
if N > 128 then
return 8;
elsif N > 64
return 7;
elsif ...
elsif N > 0 then
return 1;
end if;
Pascal.
--
--|------------------------------------------------------
--| Pascal Obry Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--| http://www.obry.net - http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 17:34 highest bit, statically determined Georg Bauhaus
2012-09-29 18:11 ` Pascal Obry
@ 2012-09-29 18:57 ` Bill Findlay
2012-09-29 19:16 ` Bill Findlay
2012-09-30 15:39 ` Anatoly Chernyshev
2 siblings, 1 reply; 28+ messages in thread
From: Bill Findlay @ 2012-09-29 18:57 UTC (permalink / raw)
On 29/09/2012 18:34, in article
50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
<rm.dash-bauhaus@futureapps.de> wrote:
> Is there a shorter/better way of having the compiler
> find the highest bit = 1 in a static numeric constant?
>
> If N is such a constant, e.g. Some_Type'Last where
> Some_Type'Size = 8 and its bound are static, then
>
> Highest_Bit_In_Octet : constant :=
> Natural'Max
> (8 * Boolean'Pos (N / 2**7 > 0),
> Natural'Max
> (7 * Boolean'Pos (N / 2**6 > 0),
> Natural'Max
> (6 * Boolean'Pos (N / 2**5 > 0),
> Natural'Max
> (5 * Boolean'Pos (N / 2**4 > 0),
> Natural'Max
> (4 * Boolean'Pos (N / 2**3 > 0),
> Natural'Max
> (3 * Boolean'Pos (N / 2**2 > 0),
> Natural'Max
> (2 * Boolean'Pos (N / 2**1 > 0),
> Natural'Max
> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
In my experience that sort of code, applied in non-static cases, is less
efficient than one would hope, and more obvious code works faster.
Something like the following can be readily extended to greater operand
widths:
function first_1_bit (y : octet)
return Natural is
x : octet;
r : Natural;
begin
if y = 0 then return 0; end if;
if (y / 16) /= 0 then
r := 4; x := y / 16;
else
r := 0; x := y;
end if;
if (x / 4) /= 0 then
r := r + 2; x := x / 4;
end if;
if (x / 2) /= 0 then
r := r + 1;
end if;
return r + 1;
end first_1_bit;
It looks fairly inline-able, and foldable for a static value of y.
--
Bill Findlay
with blueyonder.co.uk;
use surname & forename;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 18:11 ` Pascal Obry
@ 2012-09-29 18:59 ` Georg Bauhaus
2012-09-29 19:18 ` Georg Bauhaus
0 siblings, 1 reply; 28+ messages in thread
From: Georg Bauhaus @ 2012-09-29 18:59 UTC (permalink / raw)
On 29.09.12 20:11, Pascal Obry wrote:
>> Highest_Bit_In_Octet : constant :=
>> Natural'Max
>> (8 * Boolean'Pos (N / 2**7 > 0),
...
>> (3 * Boolean'Pos (N / 2**2 > 0),
>> Natural'Max
>> (2 * Boolean'Pos (N / 2**1 > 0),
>> Natural'Max
>> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>
> if N > 128 then
> return 8;
> elsif N > 64
> return 7;
> elsif ...
>
> elsif N > 0 then
> return 1;
> end if;
>
The N > 2**X part is good, thanks for the answer that removed
a fair bit of fog. But the "return X" indicates that the solution
cannot be static, or can it?
There might be an expression in Ada 2012 that does it. Alas,
I cannot use Ada 2012 yet---which I should have mentioned!
Highest_Bit_In_Octet_2012 : constant :=
(if N > 2**7 then 8
elsif N > 2**6 then 7
elsif N > 2**5 then 6
elsif N > 2**4 then 5
elsif N > 2**3 then 4
elsif N > 2**2 then 3
elsif N > 2**1 then 2
elsif N > 2**0 then 1
else 0);
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 18:57 ` Bill Findlay
@ 2012-09-29 19:16 ` Bill Findlay
2012-09-29 21:36 ` Georg Bauhaus
2012-11-04 20:45 ` Yannick Duchêne (Hibou57)
0 siblings, 2 replies; 28+ messages in thread
From: Bill Findlay @ 2012-09-29 19:16 UTC (permalink / raw)
On 29/09/2012 19:57, in article CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
"Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:
> On 29/09/2012 18:34, in article
> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
> <rm.dash-bauhaus@futureapps.de> wrote:
>
>> Is there a shorter/better way of having the compiler
>> find the highest bit = 1 in a static numeric constant?
>>
>> If N is such a constant, e.g. Some_Type'Last where
>> Some_Type'Size = 8 and its bound are static, then
>>
>> Highest_Bit_In_Octet : constant :=
>> Natural'Max
>> (8 * Boolean'Pos (N / 2**7 > 0),
>> Natural'Max
>> (7 * Boolean'Pos (N / 2**6 > 0),
>> Natural'Max
>> (6 * Boolean'Pos (N / 2**5 > 0),
>> Natural'Max
>> (5 * Boolean'Pos (N / 2**4 > 0),
>> Natural'Max
>> (4 * Boolean'Pos (N / 2**3 > 0),
>> Natural'Max
>> (3 * Boolean'Pos (N / 2**2 > 0),
>> Natural'Max
>> (2 * Boolean'Pos (N / 2**1 > 0),
>> Natural'Max
>> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>
> In my experience that sort of code, applied in non-static cases, is less
> efficient than one would hope, and more obvious code works faster.
>
> Something like the following can be readily extended to greater operand
> widths:
>
> function first_1_bit (y : octet)
> return Natural is
> x : octet;
> r : Natural;
> begin
> if y = 0 then return 0; end if;
>
> if (y / 16) /= 0 then
> r := 4; x := y / 16;
> else
> r := 0; x := y;
> end if;
>
> if (x / 4) /= 0 then
> r := r + 2; x := x / 4;
> end if;
>
> if (x / 2) /= 0 then
> r := r + 1;
> end if;
>
> return r + 1;
> end first_1_bit;
>
> It looks fairly inline-able, and foldable for a static value of y.
I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
but I now see that you want the result to be static as well as the operand,
and this does not achieve that.
--
Bill Findlay
with blueyonder.co.uk;
use surname & forename;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 18:59 ` Georg Bauhaus
@ 2012-09-29 19:18 ` Georg Bauhaus
0 siblings, 0 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-09-29 19:18 UTC (permalink / raw)
On 29.09.12 20:59, Georg Bauhaus wrote:
> Highest_Bit_In_Octet_2012 : constant :=
> (if N > 2**7 then 8
Or N >= 2**7, really.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 19:16 ` Bill Findlay
@ 2012-09-29 21:36 ` Georg Bauhaus
2012-09-29 22:06 ` Georg Bauhaus
` (2 more replies)
2012-11-04 20:45 ` Yannick Duchêne (Hibou57)
1 sibling, 3 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-09-29 21:36 UTC (permalink / raw)
On 29.09.12 21:16, Bill Findlay wrote:
functionfirst_1_bit
:-)
> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
> but I now see that you want the result to be static as well as the operand,
> and this does not achieve that.
Daringly, I have tried to steal the idea and try a comparison (out of
curiosity, not for the static thing). GCC performs simple tail call
elimination (explaining the Shift parameter)!
function First_1_Bit_A (y : octet; Shift : Integer := 0) return Natural is
begin
if y >= 2**4 then
if y >= 2**6 then
return Shift + 7 + Boolean'Pos (y >= 2**7);
else
return Shift + 5 + Boolean'Pos (y >= 2**5);
end if;
else
if Y = 0 then
return 0;
else
return First_1_Bit_A (y * 2**4, Shift => -4);
end if;
end if;
end First_1_Bit_A;
Don't know if that's as readily adaptable to other word sizes, but it might
make the functionist happier. ;-)
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 21:36 ` Georg Bauhaus
@ 2012-09-29 22:06 ` Georg Bauhaus
2012-09-29 23:38 ` Bill Findlay
2012-09-30 15:01 ` Vadim Godunko
2 siblings, 0 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-09-29 22:06 UTC (permalink / raw)
On 29.09.12 23:36, Georg Bauhaus wrote:
> On 29.09.12 21:16, Bill Findlay wrote:
>
> function first_1_bit
> function First_1_Bit_A (y : octet; Shift : Integer := 0) return Natural is
first_1_bit is better by between 30% and 40% speed here.
Inlining can mean that the program runs about 4x as fast,
for each of the two functions.
(But, with GNAT, the deprecated -gnatN has *no* effect in the
case of first_1_bit_a.
Best options: -O2 -funroll-loops -gnatp -gnatn.)
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 21:36 ` Georg Bauhaus
2012-09-29 22:06 ` Georg Bauhaus
@ 2012-09-29 23:38 ` Bill Findlay
2012-09-30 15:01 ` Vadim Godunko
2 siblings, 0 replies; 28+ messages in thread
From: Bill Findlay @ 2012-09-29 23:38 UTC (permalink / raw)
On 29/09/2012 22:36, in article
506769fb$0$6580$9b4e6d93@newsspool3.arcor-online.net, "Georg Bauhaus"
<rm.dash-bauhaus@futureapps.de> wrote:
> On 29.09.12 21:16, Bill Findlay wrote:
>
> functionfirst_1_bit
>
> :-)
>
>> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
>> but I now see that you want the result to be static as well as the operand,
>> and this does not achieve that.
>
> Daringly, I have tried to steal the idea and try a comparison (out of
> curiosity, not for the static thing). GCC performs simple tail call
> elimination (explaining the Shift parameter)!
>
> function First_1_Bit_A (y : octet; Shift : Integer := 0) return Natural
> is
> begin
> if y >= 2**4 then
> if y >= 2**6 then
> return Shift + 7 + Boolean'Pos (y >= 2**7);
> else
> return Shift + 5 + Boolean'Pos (y >= 2**5);
> end if;
> else
> if Y = 0 then
> return 0;
> else
> return First_1_Bit_A (y * 2**4, Shift => -4);
> end if;
> end if;
> end First_1_Bit_A;
These bogus parameters, used to pretend that data is not intrinsically
variable, are as objectionable as using goto statements to synthesize while
loops, IMNSHO.
> Don't know if that's as readily adaptable to other word sizes, but it might
> make the functionist happier. ;-)
Fortunately, I have no interest in keeping functionists (or the adherents of
any other religion) happy. 8-)
--
Bill Findlay
with blueyonder.co.uk;
use surname & forename;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 21:36 ` Georg Bauhaus
2012-09-29 22:06 ` Georg Bauhaus
2012-09-29 23:38 ` Bill Findlay
@ 2012-09-30 15:01 ` Vadim Godunko
2 siblings, 0 replies; 28+ messages in thread
From: Vadim Godunko @ 2012-09-30 15:01 UTC (permalink / raw)
On Sunday, September 30, 2012 1:37:00 AM UTC+4, Georg Bauhaus wrote:
>
> Daringly, I have tried to steal the idea and try a comparison (out of
> curiosity, not for the static thing). GCC performs simple tail call
> elimination (explaining the Shift parameter)!
>
If you don't need static function, you can use following function (GCC can precompute its result for static value):
with Interfaces.C; use Interfaces.C;
function Bit (X : Unsigned) return Unsigned;
pragma Inline (Bit);
function Bit (X : Unsigned) return Unsigned is
function CLZ (X : Unsigned) return Unsigned;
pragma Import (Intrinsic, CLZ, "__builtin_clz");
begin
if X = 0 then
-- XXX Return what you want.
return 0;
else
return Unsigned'Size - CLZ (X);
end if;
end Bit;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 17:34 highest bit, statically determined Georg Bauhaus
2012-09-29 18:11 ` Pascal Obry
2012-09-29 18:57 ` Bill Findlay
@ 2012-09-30 15:39 ` Anatoly Chernyshev
2012-09-30 18:36 ` Shark8
2012-10-01 8:07 ` Georg Bauhaus
2 siblings, 2 replies; 28+ messages in thread
From: Anatoly Chernyshev @ 2012-09-30 15:39 UTC (permalink / raw)
Ouch...
with ada.numerics.elementary_functions;
use ada.numerics.elementary_functions;
Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));
I didn't check it for speed though. Pros that it doesn't depend on the size.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-30 15:39 ` Anatoly Chernyshev
@ 2012-09-30 18:36 ` Shark8
2012-10-01 8:07 ` Georg Bauhaus
1 sibling, 0 replies; 28+ messages in thread
From: Shark8 @ 2012-09-30 18:36 UTC (permalink / raw)
On Sunday, September 30, 2012 9:39:41 AM UTC-6, Anatoly Chernyshev wrote:
>
> with ada.numerics.elementary_functions;
> use ada.numerics.elementary_functions;
> Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));
>
> I didn't check it for speed though. Pros that it doesn't depend on the size.
Nice!
Sometimes we get a little too caught-up in the problem-minutia we forget what the problem's really about. -- That, and some of these attributes aren't used enough to put them in the forefront of your mind when you hit a problem that can use them nicely.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-30 15:39 ` Anatoly Chernyshev
2012-09-30 18:36 ` Shark8
@ 2012-10-01 8:07 ` Georg Bauhaus
2012-10-01 8:11 ` Georg Bauhaus
2012-10-01 8:52 ` Anatoly Chernyshev
1 sibling, 2 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-01 8:07 UTC (permalink / raw)
On 30.09.12 17:39, Anatoly Chernyshev wrote:
> Ouch...
> with ada.numerics.elementary_functions;
> use ada.numerics.elementary_functions;
> Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));
>
> I didn't check it for speed though. Pros that it doesn't depend on the size.
I did. And this time I had the program actually call the randomizing
Initialize I had written for the test data. .-/ Results have changed
in favor of the recursive first_1_bit_a. The test is running on a laptop,
so it likely says little about results on a microcontroller.
x an array of 12_000 octets, 10_000 iterations for each test.
First row : Count(f(x_{k}) = f(x_{k + 1})),
second row : time in seconds
68580000 2.635991000 -- f is first_1_bit
68580000 2.036651000 -- f is first_1_bit_a
68580000 27.735934000 -- f is first_1_bit_log
with inline expansion:
68580000 1.687923000
68580000 1.447859000
68580000 24.481472000
Slightly faster in both cases when translation suppresses checks,
the integer versions more than the FPT version.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 8:07 ` Georg Bauhaus
@ 2012-10-01 8:11 ` Georg Bauhaus
2012-10-01 8:52 ` Anatoly Chernyshev
1 sibling, 0 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-01 8:11 UTC (permalink / raw)
On 01.10.12 10:07, Georg Bauhaus wrote:
> First row : Count(f(x_{k}) = f(x_{k + 1})),
> second row : time in seconds
%s/row/column/
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 8:07 ` Georg Bauhaus
2012-10-01 8:11 ` Georg Bauhaus
@ 2012-10-01 8:52 ` Anatoly Chernyshev
2012-10-01 21:30 ` Georg Bauhaus
2012-10-04 10:01 ` kalvin.news
1 sibling, 2 replies; 28+ messages in thread
From: Anatoly Chernyshev @ 2012-10-01 8:52 UTC (permalink / raw)
>
> 68580000 1.687923000
>
> 68580000 1.447859000
>
> 68580000 24.481472000
Yes, that could be expected. Here's the draft lightning-fast version:
procedure xx is
last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
N:natural;
begin
...
Highest_Bit_In_Octet:=last_bit_a(N);
...
end xx;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 8:52 ` Anatoly Chernyshev
@ 2012-10-01 21:30 ` Georg Bauhaus
2012-10-01 22:55 ` Shark8
2012-10-02 11:03 ` Brian Drummond
2012-10-04 10:01 ` kalvin.news
1 sibling, 2 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-01 21:30 UTC (permalink / raw)
On 01.10.12 10:52, Anatoly Chernyshev wrote:
> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
68580000 2.653934000
68580000 2.021029000
68580000 27.702262000
68580000 1.173348000 -- first_1_bit_table
I guess the approaches can be used together for larger N-tets.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 21:30 ` Georg Bauhaus
@ 2012-10-01 22:55 ` Shark8
2012-10-01 23:25 ` Georg Bauhaus
2012-10-02 11:03 ` Brian Drummond
1 sibling, 1 reply; 28+ messages in thread
From: Shark8 @ 2012-10-01 22:55 UTC (permalink / raw)
I wouldn't be surprised if you could make it faster by making it a constant.
Refactor something like:
Type Light_Vector is array(0..255) of natural;
last_bit_a: Constant Light_Vector:=
(0|1=>0, 2|3=>1, 4..7=>2, 8..15=>3, 16..31=>4, 32..63=>5, 64..127=>6, 128..255=>7);
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 22:55 ` Shark8
@ 2012-10-01 23:25 ` Georg Bauhaus
0 siblings, 0 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-01 23:25 UTC (permalink / raw)
On 02.10.12 00:55, Shark8 wrote:
> I wouldn't be surprised if you could make it faster by making it a constant.
It is a constant. Making it variable does not make a difference, though.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 21:30 ` Georg Bauhaus
2012-10-01 22:55 ` Shark8
@ 2012-10-02 11:03 ` Brian Drummond
2012-10-03 9:30 ` kalvink65
2012-10-04 8:25 ` Stephen Leake
1 sibling, 2 replies; 28+ messages in thread
From: Brian Drummond @ 2012-10-02 11:03 UTC (permalink / raw)
On Mon, 01 Oct 2012 23:30:24 +0200, Georg Bauhaus wrote:
> On 01.10.12 10:52, Anatoly Chernyshev wrote:
>> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6,
>> 128..255=>7);
>
> 68580000 2.653934000 68580000 2.021029000 68580000 27.702262000
> 68580000 1.173348000 -- first_1_bit_table
>
> I guess the approaches can be used together for larger N-tets.
Just for completeness,
function first_bit_case(N:Octet) return natural is
begin
case N is
when 0 => return 0;
when 1 => return 1;
when 2..3 => return 2;
when 4..7 => return 3;
when 8..15 => return 4;
when 16..31 => return 5;
when 32..63 => return 6;
when 64..127 => return 7;
when others => return 8;
end case;
end first_bit_case;
Here (on an Atom netbook) it measures about the same as the equivalent if
chain; faster than the recursive versions but slower than the table.
--Z := Z + first_1_bit_ifchain(Data(i)); -- real 0m3.208s
--Z := Z + first_bit_table(Data(i)); -- real 0m1.971s
--Z := Z + first_1_bit(Data(i)); -- real 0m4.672s
--Z := Z + First_1_Bit_A(Data(i)); -- real 0m3.937s
Z := Z + first_bit_case(Data(i)); -- real 0m3.272s
The Ada-2012 case expression was no faster.
- Brian
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-02 11:03 ` Brian Drummond
@ 2012-10-03 9:30 ` kalvink65
2012-10-03 18:54 ` Georg Bauhaus
2012-10-04 8:25 ` Stephen Leake
1 sibling, 1 reply; 28+ messages in thread
From: kalvink65 @ 2012-10-03 9:30 UTC (permalink / raw)
How about binary search algorithm with constant execution time:
Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
(if N > (2**4)-1 then -- determine upper or lower nibble
-- upper nibble
if N > (2**6)-1
-- bits 7 and 6
if N > (2**7)-1 then
7
else
6
else
-- bits 5 and 4
if N > (2**5)-1 then
5
else
4
else
-- lower nibble
if N > (2**2)-1 then
-- bits 3 and 2
if N > (2**3)-1 then
3
else
2
else
-- bits 1 and 0
if N > (2**1)-1 then
1
else
0);
Disclaimer: I am not an Ada programmer, so this might not compile, but describes the idea anyway.
- Kalvin
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-03 9:30 ` kalvink65
@ 2012-10-03 18:54 ` Georg Bauhaus
2012-10-04 7:46 ` Georg Bauhaus
0 siblings, 1 reply; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-03 18:54 UTC (permalink / raw)
<kalvink65@gmail.com> wrote:
> How about binary search algorithm with constant execution time:
>
> Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
> (if N > (2**4)-1 then -- determine upper or lower nibble
> -- upper nibble
> if N > (2**6)-1
> -- bits 7 and 6
> if N > (2**7)-1 then
>
Isn't this about the same as the recursive one?
(It uses Boolean'Pos around the third if.)
Also, I don't think its complexity is constant, since the number
of conditionals depends on the position of the first 1 bit.
That dependence is gone with the table.
Relative performance might depend on whether shift
and jump is more expensive than another branch of
conditionals. I'm guessing.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-03 18:54 ` Georg Bauhaus
@ 2012-10-04 7:46 ` Georg Bauhaus
0 siblings, 0 replies; 28+ messages in thread
From: Georg Bauhaus @ 2012-10-04 7:46 UTC (permalink / raw)
On 03.10.12 20:54, Georg Bauhaus wrote:
> <kalvink65@gmail.com> wrote:
>> How about binary search algorithm with constant execution time:
>>
>> Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
>> (if N > (2**4)-1 then -- determine upper or lower nibble
>> -- upper nibble
>> if N > (2**6)-1
>> -- bits 7 and 6
>> if N > (2**7)-1 then
>>
>
> Isn't this about the same as the recursive one?
> (It uses Boolean'Pos around the third if.)
> Also, I don't think its complexity is constant,
Ouch. I have thought again, it has constant execution time.
For the recursive one, the above one, and the one using a table,
respectively, I get, in seconds:
1.62, 1.57, 0.95
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-02 11:03 ` Brian Drummond
2012-10-03 9:30 ` kalvink65
@ 2012-10-04 8:25 ` Stephen Leake
1 sibling, 0 replies; 28+ messages in thread
From: Stephen Leake @ 2012-10-04 8:25 UTC (permalink / raw)
Brian Drummond <brian@shapes.demon.co.uk> writes:
> On Mon, 01 Oct 2012 23:30:24 +0200, Georg Bauhaus wrote:
>
>> On 01.10.12 10:52, Anatoly Chernyshev wrote:
>>> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6,
>>> 128..255=>7);
>>
>> 68580000 2.653934000 68580000 2.021029000 68580000 27.702262000
>> 68580000 1.173348000 -- first_1_bit_table
>>
>> I guess the approaches can be used together for larger N-tets.
>
> Just for completeness,
>
> function first_bit_case(N:Octet) return natural is
> begin
> case N is
> when 0 => return 0;
> when 1 => return 1;
> when 2..3 => return 2;
> when 4..7 => return 3;
> when 8..15 => return 4;
> when 16..31 => return 5;
> when 32..63 => return 6;
> when 64..127 => return 7;
> when others => return 8;
> end case;
> end first_bit_case;
Even better; binary search if/then/else instead of a linear case
statement; that cuts the number of compares significantly, especially
for larger word sizes.
--
-- Stephe
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-01 8:52 ` Anatoly Chernyshev
2012-10-01 21:30 ` Georg Bauhaus
@ 2012-10-04 10:01 ` kalvin.news
2012-10-05 7:50 ` Anatoly Chernyshev
1 sibling, 1 reply; 28+ messages in thread
From: kalvin.news @ 2012-10-04 10:01 UTC (permalink / raw)
maanantai, 1. lokakuuta 2012 11.52.43 UTC+3 Anatoly Chernyshev kirjoitti:
> >
>
> > 68580000 1.687923000
>
> >
>
> > 68580000 1.447859000
>
> >
>
> > 68580000 24.481472000
>
>
>
> Yes, that could be expected. Here's the draft lightning-fast version:
>
>
>
> procedure xx is
>
> last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
>
> N:natural;
>
> begin
>
> ...
>
> Highest_Bit_In_Octet:=last_bit_a(N);
>
> ...
>
> end xx;
This can be optimised for improved size so that we create a lookup table only for a nibble values (0..15), and divide the handling into two parts according to whether the higher nibble is zero or non-zero. The end result would be a slighter slower execution speed but less code space. And this method can easily be extended to larger data sizes, too.
- Kalvin
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-04 10:01 ` kalvin.news
@ 2012-10-05 7:50 ` Anatoly Chernyshev
2012-10-05 8:38 ` Anatoly Chernyshev
0 siblings, 1 reply; 28+ messages in thread
From: Anatoly Chernyshev @ 2012-10-05 7:50 UTC (permalink / raw)
On Thursday, October 4, 2012 2:01:50 PM UTC+4, kalvi...@gmail.com wrote:
> maanantai, 1. lokakuuta 2012 11.52.43 UTC+3 Anatoly Chernyshev kirjoitti:
>
> > >
>
> >
>
> > > 68580000 1.687923000
>
> >
>
> > >
>
> >
>
> > > 68580000 1.447859000
>
> >
>
> > >
>
> >
>
> > > 68580000 24.481472000
>
> >
>
> >
>
> >
>
> > Yes, that could be expected. Here's the draft lightning-fast version:
>
> >
>
> >
>
> >
>
> > procedure xx is
>
> >
>
> > last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
>
> >
>
> > N:natural;
>
> >
>
> > begin
>
> >
>
> > ...
>
> >
>
> > Highest_Bit_In_Octet:=last_bit_a(N);
>
> >
>
> > ...
>
> >
>
> > end xx;
>
>
>
> This can be optimised for improved size so that we create a lookup table only for a nibble values (0..15), and divide the handling into two parts according to whether the higher nibble is zero or non-zero. The end result would be a slighter slower execution speed but less code space. And this method can easily be extended to larger data sizes, too.
>
>
>
> - Kalvin
If you play with the memory optimization (I'm not very good at it), the array above will be made of 3 bit integers (0 to 7), which occupy lousy 3*256/8= 96 bytes of memory. Laughable by today's standards. Even if you go for long_long_long..._integers, the table will be quite small.
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-10-05 7:50 ` Anatoly Chernyshev
@ 2012-10-05 8:38 ` Anatoly Chernyshev
0 siblings, 0 replies; 28+ messages in thread
From: Anatoly Chernyshev @ 2012-10-05 8:38 UTC (permalink / raw)
> If you play with the memory optimization (I'm not very good at it), the array above will be made of 3 bit integers (0 to 7), which occupy lousy 3*256/8= 96 bytes of memory. Laughable by today's standards. Even if you go for long_long_long..._integers, the table will be quite small.
Here we go:
with Text_IO;
use Text_IO;
procedure xx is
type smallint is range 0..7;
type smallint_a is array(0..255) of smallint;
for smallint_a'Component_Size use 3;
last_bit_a: smallint_a:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
begin
put_line (integer'Image (smallint_a'size/8));
end xx;
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-09-29 19:16 ` Bill Findlay
2012-09-29 21:36 ` Georg Bauhaus
@ 2012-11-04 20:45 ` Yannick Duchêne (Hibou57)
2012-11-04 22:00 ` Bill Findlay
1 sibling, 1 reply; 28+ messages in thread
From: Yannick Duchêne (Hibou57) @ 2012-11-04 20:45 UTC (permalink / raw)
Le Sat, 29 Sep 2012 21:16:01 +0200, Bill Findlay
<yaldnif.w@blueyonder.co.uk> a écrit:
>
> On 29/09/2012 19:57, in article
> CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
> "Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:
>
>> On 29/09/2012 18:34, in article
>> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
>> <rm.dash-bauhaus@futureapps.de> wrote:
>>
>>> Is there a shorter/better way of having the compiler
>>> find the highest bit = 1 in a static numeric constant?
>>>
>>> If N is such a constant, e.g. Some_Type'Last where
>>> Some_Type'Size = 8 and its bound are static, then
>>>
>>> Highest_Bit_In_Octet : constant :=
>>> Natural'Max
>>> (8 * Boolean'Pos (N / 2**7 > 0),
>>> Natural'Max
>>> (7 * Boolean'Pos (N / 2**6 > 0),
>>> Natural'Max
>>> (6 * Boolean'Pos (N / 2**5 > 0),
>>> Natural'Max
>>> (5 * Boolean'Pos (N / 2**4 > 0),
>>> Natural'Max
>>> (4 * Boolean'Pos (N / 2**3 > 0),
>>> Natural'Max
>>> (3 * Boolean'Pos (N / 2**2 > 0),
>>> Natural'Max
>>> (2 * Boolean'Pos (N / 2**1 > 0),
>>> Natural'Max
>>> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>>
>> In my experience that sort of code, applied in non-static cases, is less
>> efficient than one would hope, and more obvious code works faster.
>>
>> Something like the following can be readily extended to greater operand
>> widths:
>>
>> function first_1_bit (y : octet)
>> return Natural is
>> x : octet;
>> r : Natural;
>> begin
>> if y = 0 then return 0; end if;
>>
>> if (y / 16) /= 0 then
>> r := 4; x := y / 16;
>> else
>> r := 0; x := y;
>> end if;
>>
>> if (x / 4) /= 0 then
>> r := r + 2; x := x / 4;
>> end if;
>>
>> if (x / 2) /= 0 then
>> r := r + 1;
>> end if;
>>
>> return r + 1;
>> end first_1_bit;
>>
>> It looks fairly inline-able, and foldable for a static value of y.
>
> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
> but I now see that you want the result to be static as well as the
> operand,
> and this does not achieve that.
>
What means folding in this context?
--
“Syntactic sugar causes cancer of the semi-colons.” [1]
“Structured Programming supports the law of the excluded muddle.” [1]
[1]: Epigrams on Programming — Alan J. — P. Yale University
^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined
2012-11-04 20:45 ` Yannick Duchêne (Hibou57)
@ 2012-11-04 22:00 ` Bill Findlay
0 siblings, 0 replies; 28+ messages in thread
From: Bill Findlay @ 2012-11-04 22:00 UTC (permalink / raw)
On 04/11/2012 20:45, in article op.wm9nx2i3ule2fv@cardamome, "Yannick
Duch�ne (Hibou57)" <yannick_duchene@yahoo.fr> wrote:
> Le Sat, 29 Sep 2012 21:16:01 +0200, Bill Findlay
> <yaldnif.w@blueyonder.co.uk> a �crit:
>
>>
>> On 29/09/2012 19:57, in article
>> CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
>> "Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:
>>
>>> On 29/09/2012 18:34, in article
>>> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
>>> <rm.dash-bauhaus@futureapps.de> wrote:
>>>
>>>> Is there a shorter/better way of having the compiler
>>>> find the highest bit = 1 in a static numeric constant?
>>>>
>>>> If N is such a constant, e.g. Some_Type'Last where
>>>> Some_Type'Size = 8 and its bound are static, then
>>>>
>>>> Highest_Bit_In_Octet : constant :=
>>>> Natural'Max
>>>> (8 * Boolean'Pos (N / 2**7 > 0),
>>>> Natural'Max
>>>> (7 * Boolean'Pos (N / 2**6 > 0),
>>>> Natural'Max
>>>> (6 * Boolean'Pos (N / 2**5 > 0),
>>>> Natural'Max
>>>> (5 * Boolean'Pos (N / 2**4 > 0),
>>>> Natural'Max
>>>> (4 * Boolean'Pos (N / 2**3 > 0),
>>>> Natural'Max
>>>> (3 * Boolean'Pos (N / 2**2 > 0),
>>>> Natural'Max
>>>> (2 * Boolean'Pos (N / 2**1 > 0),
>>>> Natural'Max
>>>> (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>>>
>>> In my experience that sort of code, applied in non-static cases, is less
>>> efficient than one would hope, and more obvious code works faster.
>>>
>>> Something like the following can be readily extended to greater operand
>>> widths:
>>>
>>> function first_1_bit (y : octet)
>>> return Natural is
>>> x : octet;
>>> r : Natural;
>>> begin
>>> if y = 0 then return 0; end if;
>>>
>>> if (y / 16) /= 0 then
>>> r := 4; x := y / 16;
>>> else
>>> r := 0; x := y;
>>> end if;
>>>
>>> if (x / 4) /= 0 then
>>> r := r + 2; x := x / 4;
>>> end if;
>>>
>>> if (x / 2) /= 0 then
>>> r := r + 1;
>>> end if;
>>>
>>> return r + 1;
>>> end first_1_bit;
>>>
>>> It looks fairly inline-able, and foldable for a static value of y.
>>
>> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
>> but I now see that you want the result to be static as well as the
>> operand,
>> and this does not achieve that.
>>
>
> What means folding in this context?
Compile-time evaluation, so that the end result is a compile-time known
(I do not say static, as that is a term of art in Ada) value.
--
Bill Findlay
with blueyonder.co.uk;
use surname & forename;
^ permalink raw reply [flat|nested] 28+ messages in thread
end of thread, other threads:[~2012-11-04 22:00 UTC | newest]
Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-09-29 17:34 highest bit, statically determined Georg Bauhaus
2012-09-29 18:11 ` Pascal Obry
2012-09-29 18:59 ` Georg Bauhaus
2012-09-29 19:18 ` Georg Bauhaus
2012-09-29 18:57 ` Bill Findlay
2012-09-29 19:16 ` Bill Findlay
2012-09-29 21:36 ` Georg Bauhaus
2012-09-29 22:06 ` Georg Bauhaus
2012-09-29 23:38 ` Bill Findlay
2012-09-30 15:01 ` Vadim Godunko
2012-11-04 20:45 ` Yannick Duchêne (Hibou57)
2012-11-04 22:00 ` Bill Findlay
2012-09-30 15:39 ` Anatoly Chernyshev
2012-09-30 18:36 ` Shark8
2012-10-01 8:07 ` Georg Bauhaus
2012-10-01 8:11 ` Georg Bauhaus
2012-10-01 8:52 ` Anatoly Chernyshev
2012-10-01 21:30 ` Georg Bauhaus
2012-10-01 22:55 ` Shark8
2012-10-01 23:25 ` Georg Bauhaus
2012-10-02 11:03 ` Brian Drummond
2012-10-03 9:30 ` kalvink65
2012-10-03 18:54 ` Georg Bauhaus
2012-10-04 7:46 ` Georg Bauhaus
2012-10-04 8:25 ` Stephen Leake
2012-10-04 10:01 ` kalvin.news
2012-10-05 7:50 ` Anatoly Chernyshev
2012-10-05 8:38 ` Anatoly Chernyshev
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox