Databases
StackOverflow2013
Postsdbo
POhow to improve multi-dimentional bit array comparison performance in c or c++
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POhow to improve multi-dimentional bit array comparison performance in c or c++
    primarykey
    data
    text
    <p>I have the following three-dimensional bit array(for a bloom filter):</p> <pre><code>unsigned char P_bit_table_[P_ROWS][ROWS][COLUMNS]; </code></pre> <p><img src="https://i.stack.imgur.com/QytAW.png" alt="enter image description here"></p> <p>the P_ROWS's dimension represents independent two-dimensional bit arrays(i.e, P_ROWS[0], P_ROWS<a href="https://i.stack.imgur.com/QytAW.png" rel="nofollow noreferrer">1</a>,P_ROWS[2] are independent bit arrays) and could be as large as 100MBs and contains data which are populated independently. The data that I am looking for could be in any of these P_ROWS and right now I am searching through it independently, which is P_ROWS[0] then P_ROWS<a href="https://i.stack.imgur.com/QytAW.png" rel="nofollow noreferrer">1</a> and so on until i get a positive or until the end of it(P_ROWS[n-1]). This implies that if n is 100 I have to do this search(bit comparison) 100 times(and this search is done very often). Some body suggested that I can improve the search performance if I could do bit grouping (use a column-major order on the row-major order array-- I DON'T KNOW HOW).</p> <p>I really need to improve the performance of the search because the program does a lot of it.</p> <p>I will be happy to give more details of my bit table implementation if required.</p> <p>Sorry for the poor language.</p> <p>Thanks for your help.</p> <p>EDIT: The bit grouping could be done in the following format: Assume the array to be :</p> <pre><code>unsigned char P_bit_table_[P_ROWS][ROWS][COLUMNS]={{(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))}, {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))}, {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))}}; </code></pre> <p>As you can see all the rows --on the third dimension-- have similar data. What I want after the grouping is like; all the a1's are in one group(as just one entity so that i can compare them with another bit for checking if they are on or off ) and all the b1's are in another group and so on.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJohn
    1. USJohn
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USDr. ABT
      1. VTFavorite
    2. VO
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USJohn
      1. VTFavorite
    3. VO
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USPih
      1. VTFavorite
    1. COIs my question not clear?
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USJohn
    2. COuhm, are you looking for P_bit_table_[COLUMNS][ROWS][P_ROWS] instead of P_bit_table_[P_ROWS][ROWS][COLUMNS] ??? (actually, the definition doesn't matter, the access does) IMHO you're accessing large amounts of data, it can't be very fast. Also, access to 8bit values is quite slow on 32 bit machines. What kind of patterns you're looking for? 1 byte patterns? multibyte patterns? 1 row patterns?
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USAgent_L
    3. CO@Agent_L: I am not sure if I have understood the "access patterns" you described. If you mean the size of the 'group' I am sure it is a multibyte sized array. For example if there are 16 independent rows then we will have to group the bits of these rows in to 2byte sized groups. The number of the rows is always a power of two.
      singulars
      1. POhow to improve multi-dimentional bit array comparison performance in c or c++
      1. USJohn
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload