Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I want to find a way to speed up this code.

if you look at the condition of If calculated Then in the code below, this is what slowing down the code.

While the code provided seem fast with Const initBit = 4 try it with something over 12.

I want to be able to use this code (with calculated param as True) with initBit of 20 or more.

Beware that 20 or more might require a gig or more of ram and/or compiled as x64.

C# code (converted with an online tool from VB.NET):

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

static class Module1
{
public static void Main()
{
    Console.WindowHeight = 59;
    int initBit = 4;
    var sw = Stopwatch.StartNew();
    initBits(initBit, false);
    sw.Stop();
    printResult(sw, false);

    sw = Stopwatch.StartNew();
    initBits(initBit, true);
    sw.Stop();
    printResult(sw, true);

    Console.Read();
}

private static int maxBits;
private static int[] CountBit;
private static int[] CalculatedBit;

private static int[] MapBit;
private static void initBits(int maxBit, bool calculated)
{
    int[] calc = null;
    bool calcOk = false;
    int calcOkPos = 0;
    List<int> calcResult = new List<int>();
    int findPos = 0;

    maxBits = ((1 << maxBit)) - 1;
    calc = new int[maxBits + 1];
    CountBit = new int[maxBits + 1];
    MapBit = new int[maxBits + 1];

    for (var i = 0; i <= maxBits; i++)
    {
        CountBit[i] = getBitCount(i);
    }

    calcResult.Add(0);

    for (var i = maxBits; i >= 1; i += -1)
    {
        for (var j = 0; j <= CountBit[i] - 1; j++)
        {
            calc[j] = getBitValue(i, j);
        }
        calcOk = false;
        if (calculated)
        {
            findPos = calcResult.IndexOf(calc[0], 0);

            while (findPos != -1)
            {
                calcOk = true;
                for (var k = 0; k <= CountBit[i] - 1; k++)
                {
                    calcOk = calcOk && calcResult[findPos + k] == calc[k];
                    if (!calcOk)
                        break; // TODO: might not be correct. Was : Exit For
                }
                if (calcOk)
                {
                    calcOkPos = findPos;
                    break; // TODO: might not be correct. Was : Exit While
                }
                findPos = calcResult.IndexOf(calc[0], findPos + 1);
            }
        }

        if (!calcOk)
        {
            MapBit[i] = calcResult.Count;
            for (var j = 0; j <= CountBit[i] - 1; j++)
            {
                calcResult.Add(calc[j]);
            }
        }
        else
        {
            MapBit[i] = calcOkPos;
        }
    }
    CalculatedBit = calcResult.ToArray();
    calcResult.Clear();
}

private static int getBitCount(int bits)
{
    bits = bits - ((bits >> 1) & 0x55555555);
    bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
    return ((bits + (bits >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}

private static int getBitValue(int bits, int pos)
{
    for (var k = 0; k <= pos - 1; k++)
    {
        bits = bits & bits - 1;
    }
    return bits ^ bits & (bits - 1);
}


private static void printResult(Stopwatch sw, bool calculated)
{
    StringBuilder sb = new StringBuilder();
    sb.AppendLine("    Calculated : " + calculated.ToString() + Environment.NewLine + "    maxBits : " + maxBits.ToString() + " (" + getBitCount(maxBits) + ")" + Environment.NewLine + "    CalculatedBit.Length : " + CalculatedBit.Length.ToString());
    //if initBit is 6 or less
    if (CalculatedBit.Length <= 65)
    {
        sb.AppendLine(Environment.NewLine + "    Started with" + Environment.NewLine + "    Number : Value");
        for (var i = 0; i <= maxBits; i++)
        {
            sb.Append(i.ToString().PadLeft(10) + " : ");
            for (var j = 0; j <= (CountBit[i] == 0 ? 1 : CountBit[i] - 1); j++)
            {
                sb.Append(getBitValue(i, j).ToString() + " ");
            }
            sb.AppendLine("");
        }
        sb.AppendLine(Environment.NewLine + "    Index : Value");
        for (var i = 0; i <= CalculatedBit.GetUpperBound(0); i++)
        {
            sb.AppendLine(i.ToString().PadLeft(9) + " : " + CalculatedBit[i].ToString());
        }
        sb.AppendLine(Environment.NewLine + "    Number : MapBit : CountBit : Value");
        for (var i = 0; i <= maxBits; i++)
        {
            sb.Append(i.ToString().PadLeft(10) + " : " + MapBit[i].ToString().PadLeft(6) + " : " + CountBit[i].ToString().PadLeft(8) + " : ");
            for (var k = 0; k <= (CountBit[i] == 0 ? 1 : CountBit[i] - 1); k++)
            {
                sb.Append(CalculatedBit[MapBit[i] + k].ToString() + " ");
            }
            sb.AppendLine("");
        }
    }
    sb.AppendLine(Environment.NewLine + "    Took: " + sw.ElapsedMilliseconds + "ms" + Environment.NewLine);
    Console.Write(sb.ToString());
    Debug.Write(sb.ToString());
}

}

Make sure, if you do create a VB.NET project, to "check" the setting "Remove integer overflow checks" in "Advanced Compiler Settings" in "Compile" tab in the project "Properties" to let the magic of getBitCount function work.

VB.NET Code:

Imports System.Text

Module Module1
Sub Main()
    Console.WindowHeight = 59
    Const initBit = 4
    Dim sw = Stopwatch.StartNew
    initBits(initBit, False)
    sw.Stop()
    printResult(sw, False)

    sw = Stopwatch.StartNew
    initBits(initBit, True)
    sw.Stop()
    printResult(sw, True)

    Console.Read()
End Sub

Private maxBits As Integer
Private CountBit() As Integer
Private CalculatedBit() As Integer
Private MapBit() As Integer

Private Sub initBits(ByVal maxBit As Integer, ByVal calculated As Boolean)
    Dim calc() As Integer
    Dim calcOk As Boolean
    Dim calcOkPos As Integer
    Dim calcResult As New List(Of Integer)
    Dim findPos As Integer

    maxBits = ((1 << maxBit)) - 1
    ReDim calc(maxBits)
    ReDim CountBit(maxBits)
    ReDim MapBit(maxBits)

    For i = 0 To maxBits
        CountBit(i) = getBitCount(i)
    Next

    calcResult.Add(0)

    For i = maxBits To 1 Step -1
        For j = 0 To CountBit(i) - 1
            calc(j) = getBitValue(i, j)
        Next
        calcOk = False
        If calculated Then
            findPos = calcResult.IndexOf(calc(0), 0)

            While findPos <> -1
                calcOk = True
                For k = 0 To CountBit(i) - 1
                    calcOk = calcOk AndAlso calcResult(findPos + k) = calc(k)
                    If Not calcOk Then Exit For
                Next
                If calcOk Then
                    calcOkPos = findPos
                    Exit While
                End If
                findPos = calcResult.IndexOf(calc(0), findPos + 1)
            End While
        End If

        If Not calcOk Then
            MapBit(i) = calcResult.Count
            For j = 0 To CountBit(i) - 1
                calcResult.Add(calc(j))
            Next
        Else
            MapBit(i) = calcOkPos
        End If
    Next
    CalculatedBit = calcResult.ToArray
    calcResult.Clear()
End Sub

Private Function getBitCount(bits As Integer) As Integer
    bits = bits - ((bits >> 1) And &H55555555)
    bits = (bits And &H33333333) + ((bits >> 2) And &H33333333)
    Return ((bits + (bits >> 4) And &HF0F0F0F) * &H1010101) >> 24
End Function

Private Function getBitValue(bits As Integer, pos As Integer) As Integer
    For k = 0 To pos - 1
        bits = bits And bits - 1
    Next
    Return bits Xor bits And (bits - 1)
End Function


Private Sub printResult(ByVal sw As Stopwatch, ByVal calculated As Boolean)
    Dim sb As New StringBuilder
    sb.AppendLine("    Calculated : " & calculated.ToString & Environment.NewLine & "    maxBits : " & maxBits.ToString & " (" & getBitCount(maxBits) & ")" & Environment.NewLine & "    CalculatedBit.Length : " & CalculatedBit.Length.ToString)
    If CalculatedBit.Length <= 65 Then 'if initBit is 6 or less
        sb.AppendLine(Environment.NewLine & "    Started with" & Environment.NewLine & "    Number : Value")
        For i = 0 To maxBits
            sb.Append(i.ToString.PadLeft(10) & " : ")
            For j = 0 To If(CountBit(i) = 0, 1, CountBit(i)) - 1
                sb.Append(getBitValue(i, j).ToString & " ")
            Next
            sb.AppendLine("")
        Next
        sb.AppendLine(Environment.NewLine & "    Index : Value")
        For i = 0 To CalculatedBit.GetUpperBound(0)
            sb.AppendLine(i.ToString.PadLeft(9) & " : " & CalculatedBit(i).ToString)
        Next
        sb.AppendLine(Environment.NewLine & "    Number : MapBit : CountBit : Value")
        For i = 0 To maxBits
            sb.Append(i.ToString.PadLeft(10) & " : " & MapBit(i).ToString.PadLeft(6) & " : " & CountBit(i).ToString.PadLeft(8) & " : ")
            For k = 0 To If(CountBit(i) = 0, 1, CountBit(i)) - 1
                sb.Append(CalculatedBit(MapBit(i) + k).ToString & " ")
            Next
            sb.AppendLine("")
        Next
    End If
    sb.AppendLine(Environment.NewLine & "    Took: " & sw.ElapsedMilliseconds & "ms" & Environment.NewLine)
    Console.Write(sb.ToString)
    Debug.Write(sb.ToString)
End Sub

End Module

Result:

Calculated : False
maxBits : 15 (4)
CalculatedBit.Length : 33

Started with
Number : Value
     0 : 0 
     1 : 1 
     2 : 2 
     3 : 1 2 
     4 : 4 
     5 : 1 4 
     6 : 2 4 
     7 : 1 2 4 
     8 : 8 
     9 : 1 8 
    10 : 2 8 
    11 : 1 2 8 
    12 : 4 8 
    13 : 1 4 8 
    14 : 2 4 8 
    15 : 1 2 4 8 

Index : Value
    0 : 0
    1 : 1
    2 : 2
    3 : 4
    4 : 8
    5 : 2
    6 : 4
    7 : 8
    8 : 1
    9 : 4
   10 : 8
   11 : 4
   12 : 8
   13 : 1
   14 : 2
   15 : 8
   16 : 2
   17 : 8
   18 : 1
   19 : 8
   20 : 8
   21 : 1
   22 : 2
   23 : 4
   24 : 2
   25 : 4
   26 : 1
   27 : 4
   28 : 4
   29 : 1
   30 : 2
   31 : 2
   32 : 1

Number : MapBit : CountBit : Value
     0 :      0 :        0 : 0 
     1 :     32 :        1 : 1 
     2 :     31 :        1 : 2 
     3 :     29 :        2 : 1 2 
     4 :     28 :        1 : 4 
     5 :     26 :        2 : 1 4 
     6 :     24 :        2 : 2 4 
     7 :     21 :        3 : 1 2 4 
     8 :     20 :        1 : 8 
     9 :     18 :        2 : 1 8 
    10 :     16 :        2 : 2 8 
    11 :     13 :        3 : 1 2 8 
    12 :     11 :        2 : 4 8 
    13 :      8 :        3 : 1 4 8 
    14 :      5 :        3 : 2 4 8 
    15 :      1 :        4 : 1 2 4 8 

Took: 1ms

Calculated : True
maxBits : 15 (4)
CalculatedBit.Length : 13

Started with
Number : Value
     0 : 0 
     1 : 1 
     2 : 2 
     3 : 1 2 
     4 : 4 
     5 : 1 4 
     6 : 2 4 
     7 : 1 2 4 
     8 : 8 
     9 : 1 8 
    10 : 2 8 
    11 : 1 2 8 
    12 : 4 8 
    13 : 1 4 8 
    14 : 2 4 8 
    15 : 1 2 4 8 

Index : Value
    0 : 0
    1 : 1
    2 : 2
    3 : 4
    4 : 8
    5 : 1
    6 : 4
    7 : 8
    8 : 1
    9 : 2
   10 : 8
   11 : 1
   12 : 8

Number : MapBit : CountBit : Value
     0 :      0 :        0 : 0 
     1 :      1 :        1 : 1 
     2 :      2 :        1 : 2 
     3 :      1 :        2 : 1 2 
     4 :      3 :        1 : 4 
     5 :      5 :        2 : 1 4 
     6 :      2 :        2 : 2 4 
     7 :      1 :        3 : 1 2 4 
     8 :      4 :        1 : 8 
     9 :     11 :        2 : 1 8 
    10 :      9 :        2 : 2 8 
    11 :      8 :        3 : 1 2 8 
    12 :      3 :        2 : 4 8 
    13 :      5 :        3 : 1 4 8 
    14 :      2 :        3 : 2 4 8 
    15 :      1 :        4 : 1 2 4 8 

Took: 0ms

I will try to explain what this code does but I'm normally not good at this. (Also, English is not my primary language)

That code is a kind of a compressed cached dictionary(calculatedBit) that can rebuild a number from 2 information, the position(mapBit) and the number of bits(countBit)

I will use the result(with Calculated : True) provided to explain it.

I passed the value 4 to the method so I'm asking "create the dictionary for number 0 to 15" because 15 = 1111.

I start at 15 and loop until 1 (0 is hard-coded to be at position 0 of the calculatedBit)

For each number, I'm getting the number of bits that are 1 (and not 0) and I'm getting the value of each bits.

So let say I'm at number 6, (0110), I set countbit(6) = 2 and this array of int 2, 4

I'm looping through the dictionary to find that specific pattern: 2, 4

Since 15 is already cached(1111, countbit 4, and this list 1, 2, 4, 8) and the lookup is telling me that 2, 4 is found at position 2, I set mapbit(6) = 2

With all that cached information, I can simply rebuild the number without having to call the function getBitValue and getBitCount which are more expensive than a reference in an array.

If I want to rebuild the number 6, I can simply say; get me the position, mapbit(6), and the number of bit to sum, countbit(6) and I can simply do a LINQ call or a loop from 2 to 3 in the arrat calculatedBit and I have my number 6.

In my program, I have a huge loop that want a random bit, that is 1, from a number.

I only have to do; calculatedbit(mapbit(num) + random.next(0,countbit(num))) to get that random bit

So by precalculating everything, I'm gaining 50 to 75% in speed since I don't have to call getBitValue and getBitCount function millions of time.

Which mean I don't have to do; getBitValue(num, random.next(0,getBitCount(num)))

My problem is that caching above 14 bits (1111111111111) is VERY slow and without the lookup, it can get pretty big, 25 bits can take 2.5 gig of ram

share|improve this question
3  
I think the relevant code here is only a few lines. But because of all the WriteLining I'm not sure. –  Henk Holterman Jun 25 '12 at 17:38
    
@HenkHolterman, don't look at the printResult. it's just to see the end result –  Fredou Jun 25 '12 at 17:42
4  
This question looks like it would be better suited to Code Review. Stack Overflow isn't really for big code dumps followed by "how do I make it faster?" If it's a very short code section, sometimes it'll fly. –  Mike Bantegui Jun 25 '12 at 17:43
5  
Can you talk through a bit what this code is tryign to do, especially the bit you want optimised. The code is quite complex and the only thing that makes sense of what you are doing is counting the bits... Unfortunately your code has some confusingly named variables (eg maxBits isn't the maximum number of bits as I would have expected but seems to be the maximum value without any bits set higher than maxbits). Cleaning up some of that might make everybody's life easier. –  Chris Jun 25 '12 at 18:15
1  
@Fredou: what is the purpose of your app? Are you facing a problem that requires counting items, searching/retrieving from a collection or is it mostly compression/encoding? Have you considered standard algorithms and data structures suitable for that kind of work? For example, hash|dictionaries|associative arrays, or tree-like data structures? For dictionary-based encoding, study classic algorithms (e.g. Lempel-Ziv, etc). Cheers! –  user14433 Jun 26 '12 at 3:04
show 7 more comments

migrated from stackoverflow.com Jun 25 '12 at 17:56

This question came from our site for professional and enthusiast programmers.

1 Answer

So I found the perfect way! it was right in front of me, I just had to look at the data itself

I found the pattern that do exactly what I wanted without having to search for a pattern :-)

so i would show the code and I will try to explain it

here it is

Private Sub initBits(ByVal maxBit As Integer)

    maxBits = ((1 << maxBit)) - 1
    ReDim CountBit(maxBits)
    ReDim MapBit(maxBits)

    For i = 1 To maxBits
        CountBit(i) = getBitCount(i)
    Next

    Dim StopBit = (maxBits >> 1)
    Dim StartBit = maxBits
    Dim count As Integer = 0

    For i = StartBit To StopBit + 1 Step -2
        count += CountBit(i)
    Next

    ReDim CalculatedBit(count)
    count = 1
    For i = StartBit To StopBit + 1 Step -2
        MapBit(i) = count
        For j = 0 To CountBit(i) - 1
            CalculatedBit(count) = getBitValue(i, j)
            count += 1
        Next
    Next

    Do
        count = StartBit
        StartBit = StopBit
        StopBit = StopBit >> 1
        For i = StartBit To StopBit + 1 Step -2
            MapBit(i) = MapBit(count)
            count -= 2
        Next
    Loop Until StopBit = 0

    For i = 3 To maxBits Step 2
        MapBit(i - 1) = MapBit(i) + 1
    Next
End Sub

and now the data

Number : MapBit : CountBit : Value
     0 :      0 :        0 : 0 
     1 :      1 :        1 : 1 
     2 :      2 :        1 : 2 
     3 :      1 :        2 : 1 2 
     4 :      6 :        1 : 4 
     5 :      5 :        2 : 1 4 
     6 :      2 :        2 : 2 4 
     7 :      1 :        3 : 1 2 4 
     8 :     12 :        1 : 8 
     9 :     11 :        2 : 1 8 
    10 :      9 :        2 : 2 8 
    11 :      8 :        3 : 1 2 8 
    12 :      6 :        2 : 4 8 
    13 :      5 :        3 : 1 4 8 
    14 :      2 :        3 : 2 4 8 
    15 :      1 :        4 : 1 2 4 8 

so here is what I found out.

the dictionary i made of the odd numbers of the second half in this example; 15, 13, 11 and 9

the rest is just the same pattern, look at 7, 5, 3 and 1. this mapbit(num) reference are the same as 15, 13, 15 and 15. I do not need to loop through the dictionary like i was doing before. it's a simple logic

then the even number, it's always, take mapbit(evennumber) = mapbit(evennumber+1) +1, no need to find the pattern again.

share|improve this answer
1  
The question looks intriguing; I wish I understood what it is about though. I suspect that you need a lot less code than you have. Also, storing things in a dictionary rather than an array cannot possibly be faster. –  Leonid Aug 16 '12 at 20:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.