performance - How to find an element in a linked list of blocks (containing n elements) as fast as possible? -

my data structure linked list of blocks. block contains 31 elements of 4 byte , 1 4 byte pointer next block or null(in summary 128 bytes per block). add elements time time. if last block full, add block via pointer.

one objective use less memory (= blocks) possible , having no free space between 2 elements in block.

this setting fix. code runs on 32-bit arm cortex-a8 cpu neon pipeline.

question: how find specific element in data structure possible?

approach (right now): use sorted blocks , binary search check element (9 bit of 4 byte search criteria). if desired element not in current block jump next block. if element not in last block , last block not yet full, use result of binary search insert new element (if necessary make space using memmove within block). blocks sorted.

do have idea make faster? how search right now: (q->getposition() inline function extracts 9-bit position element via "& bitmask")

do {     // binary search algorithm (bsearch)     // http://www.google.com/codesearch/     // p?hl=en#qocvjte_vow/gcc4/trunk/gcc-     // 4.4.3/libiberty/bsearch.c&q=bsearch&sa=n&cd=2&ct=rc      base = &(block->points[0]);      if (block->next == null)     {         pointsinblock = pointsinlastblock;         stop = true;     }     else     {         block = block->next;     }      (lim = pointsinblock; lim != 0; lim >>= 1)     {         q = base + (lim >> 1);          cmp = quantizedposition - q->getposition();          if (cmp > 0)         {             // quantizedposition > q: move right             base = q + 1;             lim--;         }         else if (cmp == 0)         {             // found quantpoint             *outquantpoint = q;             return true;         }         // else move left     } } while (!stop); 

since bulk of time spent in within-block search, needs fast possible. since number of elements fixed, can unroll loop, in:

if (key < a[16]){   if (key < a[8]){     ...   }   else { // key >= a[8] && key < a[16]     ...   } } else { // key >= a[16]   if (key < a[24]){     ...   }   else { // key >= a[24]     ...   } } 

study generated assembly language , single-step in debugger, make sure compiler's giving code.

you might want write little program print out above code, hard write hand, or possibly generate macros.

added: noticed 9-bit search criterion. in case, pre-allocate array of 512 4-byte words, , index directly. that's fastest, , least code.

also added: if need keep block structure, there's way unrolled binary search. it's jon bentley method:

i = 0; if (key >= a[i+16]) += 16; if (key >= a[i+ 8]) +=  8; if (key >= a[i+ 4]) +=  4; if (key >= a[i+ 2]) +=  2; if (i < 30 && key >= a[i+ 1]) +=  1; // excludes 31 if (key == a[i]) // key found 

that's slower if-tree above, because of manipulating i, substantially less code.