[Optimization Request] BigInteger

General JUCE discussion
1

Hello everyone.  I'm using BigInteger quite a lot these days and storing / retrieving from a memoryblock.   (Bits up to 500,000 with only a few set). I've noticed i'm spending a lot of time in clearBit when loadFromMemoryBlock is called.

I've had a quick look and loadFromMemoryBlock calls setBitRangeAsInt, which calls setBit -> ensureSize(as needed) and then clearBit.

It seems ensureSize clears the bits for anything newly re-allocated so clearbit is just wasting cycles.

I'm hoping you can re-work the functions and speed up loadFromMemoryBlock?

 

Cheers!

2

I can't see the code you're talking about.. I can't see any call to clearBit that isn't needed (?)

3

Hi Jules

Line 256 from Git.  I know its needed for this function but when loading from a memoryblock its not needed.

 

void BigInteger::setBit (const int bit, const bool shouldBeSet)
{
if (shouldBeSet)
  setBit (bit);
else
  clearBit (bit);
}

 

I've added this to loadFromMemoryBlock(doesn't optimize the clear bit but pre-allocates the proper size)

void BigInteger::loadFromMemoryBlock (const MemoryBlock& data)

{

    clear();

    ensureSize(bitToIndex(((int) data.getSize()) << 3)); // Added line

    for (int i = (int) data.getSize(); --i >= 0;)

        this->setBitRangeAsInt (i << 3, 8, (uint32) data [i]);

}

 

 

4

Ok, I see what you mean. Well, that method was written for simplicity, not speed. For speed it'd need to be written without using setBitRangeAsInt, i.e. by copying the data directly a byte at a time rather than bit-per-bit. Would go much faster that way, but be more code.

5

It'd be a welcome addition.  I realize not many people would run into this, so public access to the underlying HeapBlock along with the size would work. (That way I can shoot myself in the foot with serializing and restoring it!).  I understand you might not want to expose the implementation structure however.

6

Also any benefit to to moviing to int64 as the underlying storage?  I noticed a lot of java implementations use an Array of long's for their implementation

7

No - maybe it makes sense in java, but I can't think of any advantage that'd give here. And when doing arithmetic ops it's much better for it to work on them as 32-bits, so it can use 64-bit registers to handle the overflow values.

8

Wow! That's some nice changes you made... I went from 13 seconds to restore my data down to...1.5 seconds!

 

much appreciated!