Re: Base 2 Log Method - C# Discussion Boards

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]

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

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!

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 14:13

Luc Pattyn

29-Nov-07 14:13

PIEBALDconsult wrote:
Put the noose away!

Had to look that up before I knew what it was I was to discard.

On classic architectures a switch statement constitutes the biggest semantic gap between a
programming language and the underlying hardware. And there is almost no compiler that
even comes close to the optimal code.

OTOH on a MicroChip PIC you can do a "computed goto" and stuff a code block with "return const"
instructions, that is basically a switch that implements the cheapest table lookup!
So your suggestion would fit nicely there (when coded in assembly that is).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 10:55

Luc Pattyn

29-Nov-07 10:55

Yikes.

You basically took method 3 and added some casts and some method calls.
How would this be faster?

Recursion is a valuable concept, often misused, it always has a cost associated with it.
In your creation it is not quite recursion, each nesting level needs a different method,
and to top it off, you have choosen to confuse the reader by giving them all the same
name.

BTW: MSB traditionally stands for the most significant byte or bit (the one that holds the
sign in signed integers), independent of its value, and not the highest bit set.
Example: "RS232C transmits its data LSB-first".

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 12:38

PIEBALDconsult

29-Nov-07 12:38

Luc Pattyn wrote:
How would this be faster?

Well if given a byte, ushort, or uint it wouldn't need to convert them to ulong before beginning.

Luc Pattyn wrote:
you have chosen to confuse the reader by giving them all the same name.

Of course; they all do the same thing.

Luc Pattyn wrote:
not the highest bit set.

Fine I'll rename them.

This is why I tend to post answers to Friday programming quizzes on Sunday evening; I go through a lot of false starts. I need a head start.

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 13:57

Luc Pattyn

29-Nov-07 13:57

PIEBALDconsult wrote:
Well if given a byte, ushort, or uint it wouldn't need to convert them to ulong before beginning

But now each call contains a cast??

PIEBALDconsult wrote:
Of course; they all do the same thing

I agree, at least in principle, but here it needs careful attention to see which is
calling which, and I am very much in favor of readability; since they would be private
methods, I think I would give them related but clearly different names.

PIEBALDconsult wrote:
I need a head start

Which friday we will start has not yet been decided, has it?
Anyway, I still have some extreme ideas that will take some time to implement...

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 13:59

PIEBALDconsult

29-Nov-07 13:59

Luc Pattyn wrote:
since they would be private
methods

But they wouldn't be.

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 6:02

PIEBALDconsult

29-Nov-07 6:02

Something like this?

System.Math.Floor ( System.Math.Log ( val , 2 ) )

Re: Base 2 Log Method

Skippums29-Nov-07 6:22

Skippums

29-Nov-07 6:22

I just timed this method vs. the algorithm I initially posted, as well as a new faster alg. using a binary search scheme (see my response to the post before yours), and the algorithm that you proposed is OVER 4.5 times slower than my fast method (~3 times slower than my slow method for big integers)! That is why I am attempting to devise my own integer algorithm. The double arithmetic involved in the computation is EXTREMELY expensive and unneccessary, and the slowdown is unacceptable for my application.

Jeff

Re: Base 2 Log Method

Luc Pattyn29-Nov-07 6:15

Luc Pattyn

29-Nov-07 6:15

Hi Jeff,

Skippums wrote:
Is there a better way to do this, like perhaps a binary search algorithm?

yes there is.

Seems you want the bit number of the most significant bit set.
Some CPUs have an instruction for this ("find first one" or "count leading zeroes").
Using it on x86 would mean P/Invoke to another dll (C/C++ with asm)

Without asm, the optimal approach depends on the application. So here are a few questions:

What is the range of integers you expect? (smaller range may yield faster code)
And what is the distribution? (to optimally order the operations)

final Q: is there any calculation involved in getting the input value (such as multiplying,
dividing, shifting)?

BTW: the Petes and Pauls of CP will tell you "wrong forum; try Math/Algo".

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: Base 2 Log Method

Skippums29-Nov-07 6:30

Skippums

29-Nov-07 6:30

The input value is the size of a file, in bytes. It is provided by the client to my application (we assume they are good clients and provide the info correctly). Therefore, I expect the range to be anywhere between 1,000 (1 kB) and 1,000,000,000 (1 GB). I think the fastest I can get from C# code is as noted in my response to the first person who answered my question. I would be interested to try actually writing the asm code, and importing it into my C# project to get better performance. That sounds like a fun exercise. I will post the results of it as soon as I try it!

Jeff

Re: Base 2 Log Method

Ennis Ray Lynch, Jr.29-Nov-07 6:36

Ennis Ray Lynch, Jr.

29-Nov-07 6:36

Let me know if you get assembly in C#.

Need a C# Consultant? I'm available.

Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway

Re: Base 2 Log Method

PIEBALDconsult29-Nov-07 8:58

PIEBALDconsult

29-Nov-07 8:58

Luc Pattyn wrote:
Seems you want the bit number of the most significant bit set.

That may be what he wants, but that's not what he asked for. Big Grin | :-D

Hmmm, maybe it could be done recursively...

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