Re: Base 2 Log Method - C# Discussion Boards

Re: Base 2 Log Method

led mike29-Nov-07 5:35

led mike

29-Nov-07 5:35

Skippums wrote:
like perhaps a binary search algorithm?

what? you show a single integer as input, what are you going to search? Who are you?

Re: Base 2 Log Method

Skippums29-Nov-07 6:13

Skippums

29-Nov-07 6:13

For example, the following code, which takes the middle bit of a bound (0 to 32), and attempts to perform the right shift. If the result is 0, I shifted the number too far, so I make my new range 0 to 16, take the new average (8), and try again. If the number is greater than 1 at that point, you modify the lower bound, so now I am shifting 12 bits (average of 8 and 16). Continue this cycle until you find the magic number that makes the resulting shift equal to 1. This is O(log(n)) time, vs. my initial algorithm of O(n). I did some testing of the two, and the second is far faster for randomly generated numbers, but only because most randomly generated are large. When I set the upper bound to 0x1000 (4096) on the random number size, the two algorithms broke even, taking about .95 s to do 0x1000000 (16,777,216) log base 2 method calls. The code is below...

private byte Log2_2(uint val) {
    if (val < 1)
        return byte.MaxValue;
    byte high = sizeof(uint) << 3;
    byte low  = 0, med = (byte)(high >> 1);
    uint tmp = val >> med;
    while (tmp != 1) {
        if (tmp == 0)
            high = med;
        else
            low  = med;
        med = (byte)(low + high >> 1);
        tmp = val >> med;
    }
    return med;
}

Jeff

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 7:46

Luc Pattyn

29-Nov-07 7:46

Hi Jeff,

I currently have a test fixture for your Log2_2 and some of mine;
for the same number of tests they all yield around one second.
First impression is most of the time is spent in the test fixture, not in the log2 method.
May I suggest you measure again with an empty Log2_2 to check by how much the elapsed
time does (not) drop?

Here is one of my tries:

int LP_log2_3(uint val) {
    if(val==0) return -1;
    int res=0;
    if(val>0x0000FFFF) {res+=16;val>>=16;}
    if(val>0x000000FF) {res+=8;val>>=8;}
    if(val>0x0000000F) {res+=4;val>>=4;}
    if(val>0x00000003) {res+=2;val>>=2;}
    if(val>1) res++;
    return res;
}

I feel another article coming up, comparing C#, C and asm.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this months tips:
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use PRE tags to preserve formatting when showing multi-line code snippets

Re: Base 2 Log Method

Skippums29-Nov-07 8:12

Skippums

29-Nov-07 8:12

Yep, that's what I was looking for. The results of 16,777,216 (0x1000000) calls for randomly generated integers:

                               Gross     Net
1. Linear search:             1542 ms  1091 ms
2. Binary search:              887 ms   436 ms
3. Hardcoded Conditionals:     686 ms   235 ms
4. Control (returns constant): 451 ms     0 ms

That speeds it up by a factor of about 1.85; Thanks!

Jeff

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 8:39

Luc Pattyn

29-Nov-07 8:39

Are these numbers for debug or release build?
Do you call random generator inside the timed loop or did you store its outcome somehow
beforehand?

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

Skippums29-Nov-07 8:59

Skippums

29-Nov-07 8:59

1: Release build.
2: Beforehand

Here is the code...

private Stopwatch sw = new Stopwatch();
private List<uint> m_Nums = new List<uint>(0x1000000);
private List<uint> result1 = new List<uint>(0x1000000);
private List<uint> result2 = new List<uint>(0x1000000);
private List<uint> result3 = new List<uint>(0x1000000);
private List<uint> result4 = new List<uint>(0x1000000);
...
private void button1_Click(object sender, EventArgs e) {
    m_Nums.Clear();
    result1.Clear();
    result2.Clear();
    result3.Clear();
    result4.Clear();
    Random rnd = new Random();
    for (int i = 0; i < m_Nums.Capacity; ++i)
        m_Nums.Add((uint)rnd.Next());
// Start "Block1"
    sw.Start();
    foreach (uint num in m_Nums)
        result1.Add(Log2_1(num));
    sw.Stop();
    label1.Text = sw.ElapsedMilliseconds.ToString();
    sw.Reset();
// End "Block1"
// Repeat "Block1" for methods Log2_2, Log2_3, and Log2_4
}

I even tested it in different orders (ie, calling <3,4,1,2>, etc.), to see if the order those methods were being called effects the time taken by them. They were all reasonably constant regardless of the ordering. Oh yeah, and I attempted to make your Conditional method more extensible in a for loop, but it ended up taking the same time (+-10 ms) as my binary search code. I copied it below...

if (val < 1)
    return byte.MaxValue;
int shift = sizeof(uint) << 2;
uint mask = uint.MaxValue >> shift;
int rval = 0;
do {
    if (val > mask) {
        rval += shift;
        val >>= shift;
    }
    shift >>= 1;
    mask >>= shift;
} while (shift > 0);
return (byte)rval;

Jeff

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 9:18

Luc Pattyn

29-Nov-07 9:18

Thanks for the info.

I guess a big part of the overhead is enumerating the testcases and storing the results
in the List (I did sum+=LP_log2(x); to prevent the optimizer to kick it all)

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

Skippums29-Nov-07 9:37

Skippums

29-Nov-07 9:37

I don't know if you care, but the results when operating on 64 bit integers are extremely interesting. All the methods start with a zero check, which I omitted to keep this post minimal, and myType is System.Uint64. Here are the methods and the results using the same number of operations as I did for 32 bit integers (0x1000000 each):

Method1

byte high = sizeof(myType) << 3;
byte med  = (byte)(high >> 1);
byte low  = 0;
myType tmp = val >> med;
while (tmp != 1) {
    if (tmp == 0)
        high = med;
    else
        low  = med;
    med = (byte)(low + high >> 1);
    tmp = val >> med;
}
return med;

Method2

byte shift = (byte)(sizeof(myType) << 2);
myType mask = myType.MaxValue >> shift;
byte rval = 0;
do {
    if (val > mask) {
        rval += shift;
        val >>= shift;
    }
    shift >>= 1;
    mask  >>= shift;
} while (shift > 0);
return rval;

Method3

byte res = 0;
if (val > 0xFFFFFFFF) { res += 32; val >>= 32; }
if (val > 0x0000FFFF) { res += 16; val >>= 16; }
if (val > 0x000000FF) { res +=  8; val >>=  8; }
if (val > 0x0000000F) { res +=  4; val >>=  4; }
if (val > 0x00000003) { res +=  2; val >>=  2; }
if (val > 0x00000001) ++res;
return res;

Results

           Gross     Net
Method 1  1366 ms   892 ms
Method 2  2093 ms  1619 ms
Method 3   949 ms   475 ms
Control    474 ms     0 ms

I guess that being able to exit early (as in method 1) REALLY pays off as opposed to how it is being done in method 2 (which, if you remember, tied within 10 ms for 32 bit integers).

Jeff

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 9:56

Luc Pattyn

29-Nov-07 9:56

Thanks again.

I never was much in favor of method 2 due to its number of conditional tests (2 per iteration,
one for data, one for looping), and its number of right shifts (3 per iteration).

with 64-bit quantities, I trust the JIT is
- not relying on 64-bit registers (I assume you are targetting all x86 models)
- running out of CPU registers (since needing two 32-bit regs for each variable now)

In method 3 you might try and cast the Int64 to an Int32 variable after the first test,
and use the new variable for the remainder of the method, reducing the number of 64-bit
operations.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 10:19

PIEBALDconsult

29-Nov-07 10:19

There hasn't been a Friday programming quiz for a while, maybe this could be tomorrow's?

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 10:36

Luc Pattyn

29-Nov-07 10:36

Well some would have a head start then.
May I suggest a new question: given a uint, find the next power of 2. And make it fast!

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 13:06

PIEBALDconsult

29-Nov-07 13:06

Luc Pattyn wrote:
And make it fast!

"Fast" as in "not eating clock cycles"?

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 13:23

Luc Pattyn

29-Nov-07 13:23

Exactly.

I did not mean urgent, otherwise I would have put that in the subject line Big Grin | :-D

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 13:43

PIEBALDconsult

29-Nov-07 13:43

Don't make me explain the pun.

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 14:02

Luc Pattyn

29-Nov-07 14:02

I'll try not to confuse cycles and calories. Poke tongue | ;-P

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 10:26

PIEBALDconsult

29-Nov-07 10:26

I wonder how mine would stack up; could you pass them through your test?

I started with this:

public static int
MSB
(
    ulong Subject
)
{
    int result = 63 ;

    if ( Subject != 0 )
    {
        ulong runner = 1 ;

        runner <<= result ;

        while ( ( Subject & runner ) == 0 )
        {
            result-- ;
            runner >>= 1 ;
        }
    }
    else
    {
        result = -1 ;
    }

    return ( result ) ;
}

Then, taking your idea for binary search, I did this:

public static int
MSB
(
    ulong Subject
)
{
    return
    (
        Subject > uint.MaxValue
    ?
        MSB ( (uint) ( Subject >> 32 ) ) + 32
    :
        MSB ( (uint) Subject )
    ) ;
}

public static int
MSB
(
    uint Subject
)
{
    return
    (
        Subject > ushort.MaxValue
    ?
        MSB ( (ushort) ( Subject >> 16 ) ) + 16
    :
        MSB ( (ushort) Subject )
    ) ;
}

public static int
MSB
(
    ushort Subject
)
{
    return
    (
        Subject > byte.MaxValue
    ?
        MSB ( (byte) ( Subject >> 8 ) ) + 8
    :
        MSB ( (byte) Subject )
    ) ;
}

public static int
MSB
(
    byte Subject
)
{
    int result = 7 ;

    if ( Subject != 0 )
    {
        byte runner = 128 ;

        while ( ( Subject & runner ) == 0 )
        {
            result-- ;
            runner >>= 1 ;
        }
    }
    else
    {
        result = -1 ;
    }

    return ( result ) ;
}

Re: Base 2 Log Method

Skippums29-Nov-07 10:45

Skippums

29-Nov-07 10:45

I'm not going to test your first method, because although it will perform very well on the test data I am giving it (randomly produced ulongs), it is still an O(n) operation, and I know it won't perform as well on my actual data which will mostly be on the order of 2^20. However, I did check your other method, and it was clocked at 1081/623 ms (gross/net). This compared to Luc's direct comparison method at 769/311 ms and my first binary search algorithm at 1360/902 ms.

Jeff

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 13:03

PIEBALDconsult

29-Nov-07 13:03

What about this one for the byte-sized data?

(Notice the name change.)

public static int
HighestBitSet
(
    byte Subject
)
{
    int result = -1 ;

    if ( Subject > 15 )
    {
        Subject >>= 4 ;
        result += 4 ;
    }

    if ( Subject > 3 )
    {
        Subject >>= 2 ;
        result += 2 ;
    }

    if ( Subject > 1 )
    {
        Subject >>= 1 ;
        result += 1 ;
    }

    if ( Subject > 0 )
    {
        result += 1 ;
    }

    return ( result ) ;
}

Re: Base 2 Log Method

Skippums29-Nov-07 13:21

Skippums

29-Nov-07 13:21

This won't be faster than what I have already implemented, which is directly related. It is identical in logic to the idea proposed by Luc in a previous post. This is the fastest way to do it in C# without importing external unmanaged code (I am pretty certain), but Luc's way will be slightly faster. This is because this new method will, for most values, perform an additional addition operation. For the only remaining value (0), this method will perform worse by 3 unnecessary test cases and one unnecessary initialization (of the variable result). Therefore, there exists NO condition where this code will take fewer operations than Luc's code, so I don't have to test it. However, it will still be very fast, and would improve your previous algorithm's time to within (I'm guessing) ~80 ms of Luc's. The additional time would be spent on pushing and poping data to the runtime stack in calling the various methods.

Jeff

Re: Base 2 Log Method [modified]

PIEBALDconsult29-Nov-07 14:15

PIEBALDconsult

29-Nov-07 14:15

How about

private static readonly int[] force = new int[]
{ 0 , 1 , 2 , 2 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 } ;

public static int
HighestBitSet
(
    byte Subject
)
{
    int result = -1 ;

    if ( Subject > 15 )
    {
        Subject >>= 4 ;
        result = 3 ;
    }

    return ( result + force [ Subject ] ) ;
}

-- modified at 23:36 Thursday 29th November, 2007

Whoops, left out the static, decided to add readonly as well.

-- modified at 9:55 Friday 30th November, 2007

Re: Base 2 Log Method

Skippums30-Nov-07 5:19

Skippums

30-Nov-07 5:19

Nice idea! We have a new winner...

private static readonly byte[] s_Log2Vals = new byte[]
    { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };

private byte Log2(ulong val) {
    int res = -1;
    if (val  > 0xFFFFFFFF) { res += 32; val >>= 32; }
    uint val2 = (uint)val;
    if (val2 > 0x0000FFFF) { res += 16; val2 >>= 16; }
    if (val2 > 0x000000FF) { res +=  8; val2 >>=  8; }
    if (val2 > 0x0000000F) { res +=  4; val2 >>=  4; }
    return (byte)(res + s_Array[val2]);
}

The stats are as follows:

                           Gross    Net
Cascading Types:          1046 ms  591 ms
Hard Coded Conditionals:   760 ms  305 ms
Hard Coded Cond. W/ Array: 593 ms  138 ms
Control:                   455 ms    0 ms

As you can see, this method (using your idea), only took ~90ms, which increased throughput by a factor of 2.21! Thanks,

Jeff

Re: Base 2 Log Method

PIEBALDconsult30-Nov-07 10:25

PIEBALDconsult

30-Nov-07 10:25

Skippums wrote:
using your idea

Well, actually it was Luc's.

Re: Base 2 Log Method

PIEBALDconsult3-Dec-07 11:07

PIEBALDconsult

3-Dec-07 11:07

Here's the full 256-byte lookup table version. I changed it to return 0 through 8 rather than -1 through 7, but that's not a big deal (as long as you adjust).

private static readonly byte[] highestbitset = new byte[]
{
    0 , 1 , 2 , 2 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 ,
    5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 ,
    6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 ,
    6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 ,
    7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 ,
    7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 ,
    7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 ,
    7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 ,
    8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8
} ;

public static int
HighestBitSet
(
    byte Subject
)
{
    return ( highestbitset [ Subject ] ) ;
}

Now I'm looking at LowestBitSet in a similar fashion.

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 13:39

Luc Pattyn

29-Nov-07 13:39

PIEBALDconsult wrote:
Notice the name change

Much appreciated.

FYI: on most microprocessors a straight table lookup would be the fastest here,
taking only 256B of constants in the code section. But I very much doubt this
makes sense on .NET unless there would be a way to disable array index checking
in the one method.

BTW: In the mean time I performed two experiments with floating point: storing an int
in a float basically puts the log2 in the exponent for free; all that is left to do is
to get it out again. Both methods I tried are terribly slow (BitConverter.GetBytes
insists on creating a byte array; and a union, i.e. a struct with explicit field offsets,
has way too much overhead).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 13:48

PIEBALDconsult

29-Nov-07 13:48

Luc Pattyn wrote:
straight table lookup

Or a switch?

switch ( x ) 
{
case 255 :
...
case 128 : return 8 ; break ;

...
}

No, no, it's just a joke, really, I'm not suggesting it. Put the noose away!

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.