Class Vs Pure Array Representation

Question

We need to represent huge numbers in our application. We're doing this using integer arrays. The final production should be maxed for performance. We were thinking about encapsulating our array in a class so we could add properties to be related to the array such as isNegative, numberBase and alike.

We're afraid that using classes, however, will kill us performance wise. We did a test where we created a fixed amount of arrays and set it's value through pure arrays usage and where a class was created and the array accessed through the class:

for (int i = 0; i < 10000; i++)
{
 if (createClass)
 {
  BigNumber b = new BigNumber(new int[5000], 10);
  for (int j = 0; j < b.Number.Length; j++)
  {
   b[j] = 5;
  }
 }
 else
 {
  int[] test = new int[5000];
  for (int j = 0; j < test.Length; j++)
  {
   test[j] = 5;
  }
 }
}

And it appears that using classes slows down the runnign time of the above code by a factor 6 almost. We tried the above just by encapsulating the array in a struct instead which caused the running time to be almost equal to pure array usage.

What is causing this huge overhead when using classes compared to structs? Is it really just the performance gain you get when you use the stack instead of the heap?

Edit: BigNumber just stores the array in a private variable exposed by a property. Simplified:

public class BigNumber{
  private int[] number;

  public BigNumber(int[] number) { this.number = number;}

  public int[] Number{get{return number;}}
}

Answer 1

You should profile the code when you run it and see where the time is being spent.

Also consider another language that makes it easy to use big ints.

Answer 2

You're using an integer data type to store a single digit, which is part of a really large number???

I think you're lacking some fundamental computer science understanding here.

The numerals 0-9 can be represented in 4 bits. A byte contains 8 bits. So, you can stuff 2 digits into a single byte (there's your first speed up hint).

Now, go look up how many bytes an integer is taking up (hint: it will be way more than you need to store a single digit).

What's killing performance is the use of integers, which is consuming about 4 times as much memory as you should be. Use bytes or, worst case, a character array (2 digits per byte or character) to store the numerals. It doesn't take a whole lot of logic to "pack" and "unpack" the numerals into a byte.

Answer 3

It's not surprising that the second loop is much faster than the first one. What's happening is not that the class is extraordanily slow, it's that the loop is really easy for the compiler to optimise.

As the loop ranges from 0 to test.Length-1, the compiler can tell that the index variable can never be outside of the array, so it can remove the range check when accessing the array by index.

In the first loop the compiler can't do the connection between the loop and the array, so it has to check the index against the boundaries for each item that is accessed.

There will always be a bit of overhead when you encapsulate an array inside a class, but it's not as much as the difference that you get in your test. You have chosen a sitation where the compiler is able to optimise the plain array access very well, so what you are testing is more the compilers capability to optimise the code rather than what you set out to test.

Answer 4

Without seeing your BigInteger implementation, it is very difficult to tell. However, I have two guesses.

1) Your line, with the array test, can get special handling by the JIT which removes the array bounds checking. This can give you a significant boost, especially since you're not doing any "real work" in the loop

for (int j = 0; j < test.Length; j++) // This removes bounds checking by JIT

2) Are you timing this in release mode, outside of Visual Studio? If not, that, alone, would explain your 6x speed drop, since the visual studio hosting process slows down class access artificially. Make sure you're in release mode, using Ctrl+F5 to test your timings.

Answer 5

As pointed out by Guffa, the difference is mostly bounds checking.

To guarantee that bounds checking will not ruin performance, you can also put your tight loops in an unsafe block and this will eliminate bounds checking. To do this you'll need to compile with the /unsafe option.

Answer 6

Rather than reinventing (and debugging and perfecting) the wheel, you might be better served using an existing big integer implementation, so you can get on with the rest of your project.

This SO topic is a good start.
You might also check out this CodeProject article.

Answer 7

    //pre-load the bits -- do this only ONCE
    byte[] baHi = new byte[16];
    baHi[0]=0;
    baHi[1] = 000 + 00 + 00 + 16; //0001
    baHi[2] = 000 + 00 + 32 + 00; //0010
    baHi[3] = 000 + 00 + 32 + 16; //0011
    baHi[4] = 000 + 64 + 00 + 00; //0100
    baHi[5] = 000 + 64 + 00 + 16; //0101
    baHi[6] = 000 + 64 + 32 + 00; //0110
    baHi[7] = 000 + 64 + 32 + 16; //0111
    baHi[8] = 128 + 00 + 00 + 00; //1000
    baHi[9] = 128 + 00 + 00 + 16; //1001
    //not needed for 0-9
    //baHi[10] = 128 + 00 + 32 + 00; //1010
    //baHi[11] = 128 + 00 + 32 + 16; //1011
    //baHi[12] = 128 + 64 + 00 + 00; //1100
    //baHi[13] = 128 + 64 + 00 + 16; //1101
    //baHi[14] = 128 + 64 + 32 + 00; //1110
    //baHi[15] = 128 + 64 + 32 + 16; //1111

    //-------------------------------------------------------------------------
    //START PACKING
    //load TWO digits (0-9) at a time
    //this means if you're loading a big number from
    //a file, you read two digits at a time
    //and put them into bLoVal and bHiVal
    //230942034371231235  see that '37' in the middle?
    //         ^^
    //

    byte bHiVal = 3; //0000 0011 
    byte bLoVal = 7; //0000 1011 

    byte bShiftedLeftHiVal = (byte)baHi[bHiVal]; //0011 0000  =3, shifted (48)    

    //fuse the two together into a single byte
    byte bNewVal = (byte)(bShiftedLeftHiVal + bLoVal); //0011 1011 = 55 decimal

    //now store bNewVal wherever you want to store it
    //for later retrieval, like a byte array
    //END PACKING

    //-------------------------------------------------------------------------


    Response.Write("PACKING: hi: " + bHiVal + " lo: " + bLoVal + " packed: " + bNewVal);
    Response.Write("<br>");

    //-------------------------------------------------------------------------
    //START UNPACKING
    byte bUnpackedLoByte = (byte)(bNewVal & 15);  //will yield 7
    byte bUnpackedHiByte = (byte)(bNewVal & 240); //will yield 48

    //now we need to change '48' back into '3'
    string sHiBits = "00000000" + Convert.ToString(bUnpackedHiByte, 2); //drops leading 0s, so we pad...
    sHiBits = sHiBits.Substring(sHiBits.Length - 8, 8);                 //and get the last 8 characters
    sHiBits = ("0000" + sHiBits).Substring(0, 8);                       //shift right
    bUnpackedHiByte = (byte)Convert.ToSByte(sHiBits, 2);                //and, finally, get back the original byte

    //the above method, reworked, could also be used to PACK the data,
    //though it might be slower than hitting an array.
    //You can also loop through baHi to unpack, comparing the original
    //bUnpackedHyByte to the contents of the array and return
    //the index of where you found it (the index would be the 
    //unpacked digit)

    Response.Write("UNPACKING: input: " + bNewVal + " hi: " + bUnpackedHiByte + " lo: " + bUnpackedLoByte);

    //now create your output with bUnpackedHiByte and bUnpackedLoByte,
    //then move on to the next two bytes in where ever you stored the
    //really big number
    //END UNPACKING
    //-------------------------------------------------------------------------

• Even if you just changed your INT to SHORT in your original solution you'd chop your memory requirements in half, the above takes memory down to almost a bare minimum (I'm sure someone will come along screaming about a few wasted bytes)