CODEWITHSUNDEEP
c++optimizationmemoryperformance
Fabio
Fabio

Reputation: 1505

Finding the nearest used index before a specified index in an array (Fast)

This question is related to Array of pairs of 3 bit elements
This array has 52 pairs (about 40 bytes), and I want to find the first pair before the specified one that has it's values different from 0 (used pair). The obvious solution would be to check each pair < than this one (scan from right to left), but this seems to be very inefficient if there are many unused pairs (set to 0).

This image may explain better the situation:

Pairs 0, 1 and 51 are used.
I want to find the first used pair before 51 (which is 1 here).

I tried tricks like 

if(*((int *)&array[arrayPos]) == 0) {
    arrayPos -= sizeof(int);
    pairPos -= ???
}

The problem here is that subtracting from pairPos is not that simple, because of the 6 bits/pair, so I ended with a lookup table based on some relations between pairPos and arrayPos, and all this made the solution perform like the trivial one.

Is there any way to make this lookup faster ? Another problem is that there is only 1 unused byte... maybe I can make space for another 4. If there were at least 7 I could use a bitmap of the array and it would be much faster to skip over unused pairs.

Upvotes: 2

Views: 228

Answers (4)

Fabio
Fabio

Reputation: 1505

The best solution I found was:
1. make the items 1 byte (not 6 bits than before) - thanks Skizz
2. use a bitmap to see which item is the nearest on the left. This was much faster than going back with the technique described by djna.

The speed improvements are impressive:
in one test case, from 13s it's now 6.5s
in another one, from 7.4s to 3.6s
The performance has doubled :D

Thanks again for your answers!

Upvotes: 0

starblue
starblue

Reputation: 56802

Process the 6-bit values in groups.

You could use groups of 5 values in a 32 bit word, which wastes 2 bits or about 7% space. If all values in a word are 0 then the word is zero, so it is fast to find a nonempty word, then inspect the 5 values in the word.

If you can't live with a little wasted space, use groups of 96 bits, where 96 is the least common multiple of 6 and 32. I.e. pack 16 values of 6 bits into three 32 bit words.

Upvotes: 1

djna
djna

Reputation: 55937

Can you say anything about the adjacent byte values that represent an empty pair?

I want to propose looking at the bytes rather than the bits.

Any given byte if it is to be the left hand contributer of a pair of empty 6 bits chars must fit a particular bit mask whose value depends upon his postion. ?? ?? 00 00 or ?? 00 00 00 or whatever. You can consider each byte in turn for their candidacy as a left most byte. A simple lookup table of which mask to use is possible.

Hence we don't actually have to pull out the 6bit chars before considering them.

Can we do better, having discarded a byte as a candidate, can we now skip the one to left?

In the case where our mask was 00 00 00 00 if that fails then the our neighbour to the left, yes if the first bit is set.

Does that actually make things any faster?

Upvotes: 1

Zan Lynx
Zan Lynx

Reputation: 54345

There are processor specific instructions for searching bit arrays. These may be provided as compiler intrinsic functions. Many Linux filesystems use these extensively.

__builtin_ffs() is one in GCC.

ffsll() may be POSIX although I haven't heard of it until now.

Upvotes: -1

Related Questions