Thread: Performance issue!

Originally Posted by iMalc

Don't spend any significant time on this whole 'Smart index' thing. Would you rather code some over-hyped third-hand knowledge about some home-baked attempt at speeding up searching, or would you rather learn about a well-known, well-documented, extremely efficient and simple to understand algorithm designed specifically for disk-based searching, such as the B-Tree I mentioned earlier, or perhaps the B+ Tree?

B tree's are another example of indexing the search. Any way that provides improved info on where to start and/or stop the search, is a type of indexing.

Compare a plain binary search, with an indexed binary search, of 100,000 records, for example:

Plain Binary search
==============
Range: records from 1 to 100,000

Requires up to 15 HD seeks per search

Indexed or Smart Binary search
======================
Range: varies, depending on the data, your RAM, etc. With just an index of 5,000 entries,
the range is decreased to 100,000/5,000, or *just 20 records* to be searched.

Requires up to 4 HD seeks per search.

Perhaps an expert opinion would help: Here, an expert computer cryptologist, is writing about a brute force attack on their own algorithm, and DES, which involves very heavy disk access:

Code:

The problem of speed of the attack lies in the slow access to the disk. The simple binary search method cannot
be used, as it needs several tens of hours: If the table contains ~1011 billion entries, then to look up a single entry we
need log2(1011) = 38 disk accesses. If one disk access takes ~4 ms, then to look up one million entries we need 
106 × 38 × 4 ms = 152 000 s > 42 hours!

One approach that may speedup the look up consists in dividing the table into sectors of constant length. 
The values at boundaries of sectors are then stored in a special table that is small enough to fit into RAM (e.g. 16 GB). 
When searching the entry, we first run the binary search in the RAM table to find in which sector the entry is 
potentially found. Then the sector is loaded from the disk into RAM and (binary) search is finalized.

The RAM table, is the index. They use an Indexed or Smart Binary, search.

The Smart Index searching algo just takes advantage of the HD ability to read sequential records much faster than it can read records from random locations on the disk. Smart Indexing can't be used to any advantage over Indexed Binary Search, if the next record in the sorted records file, is not physically adjacent to the next larger record in the sorted records.

That is, if you're sorting your records through pointers or an index already, rather than the actual record ID, then Smarter Index will have to do random disk seeks, just like the Smart Binary search.

Both the Smart Index search, and the Smart Binary search will kick plain Binary search's butt, up and down the field.

If you can't see that, it's time you quit riding on that short bus, isn't it?

R/L has unfortunately insinuated itself into my programming time, but I'll throw up something when I get some time.

What are you trying to test, a search against 100 records that probably fit in a single disk page?

Also, you should be searching for the same keys in each search to properly test two algorithms, not different keys for each search.

Quite right, Perspective. I was hoping that the OP would either post up a link to some sample data, or just test it on his data, and report the results. I sent him a PM, but have received no reply.

One thing should be clear - in a search of anything that is significantly slower than RAM, you benefit from limiting the range of the search in RAM, before you have the much slower HD, finish it up.

Whether that limited range is derived from an index array, or something else, really doesn't matter. Anything you can do to reduce the range of the search very quickly, by 90%, (from 100 records to 10 in this case), is going to reduce the time needed to finish the search.

This is a more persuasive comparison:

There are now 32,000 records in the data file

They are searching for the same ID numbers.

Each record now has 47 bytes, and includes a company name, which varies from record to record.

As the records get bigger, and as the number of records in the file increases, the better performance of an indexed search will become larger.

The original file: had 100 records with a size of 36 bytes/record iirc. The average time for the the indexed search was 3.9 X better than that of the binary search, in the test range of 100,000 to 300,000 searches.

The new file has 32,000 records with a size of 47 bytes/record. The average time for the indexed search is 6.9 X better than that of the binary search, in this test range of 100,000 to 300,000 searches.

If you want to make the indexed search still faster, just extend the if statements that seek a good low and high bounds for the search and/or increase the size of the index array.

If you want the data file so you can run it yourself, just let me know. I'll upload it to MegaUpload and post the url to it.

Code:

/* A HD file search comparison program. Compares a binary search, 
with a smart index search. By Adak, March 18, 2009.

Status: ok in limited testing
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SearchNum 300000

char myfile[] = "records.bin";
FILE *pfile = NULL;

typedef struct customer {
   unsigned long id;
   char name[20];
   char company[20];
   char state[3];
}Customer;

int get_person(Customer *pcustomer);  //input
void showIt(void);                   //show all records
int binsearch(unsigned long target, unsigned long MaxRecords); 
int smartIndex(unsigned long target, unsigned long low);  

int main(void) {
   clock_t start, stop;
   time_t t;
   int goal, gap, halfgap;   
   unsigned long i, gotIt, searches, target, low, mid, high, indxhit;
   unsigned long MaxRecords, MaxIndex;
   char choice;
   unsigned long *idx;
   Customer member;                  //declares a customer struct
   Customer *pmember = &member;      //ptr to the customer member

   pfile = fopen(myfile, "rb");
   fseek(pfile, 0L, SEEK_END);
   i = ftell(pfile);
   fseek(pfile, 0L, SEEK_SET);
   MaxRecords = i/sizeof member;
   printf("\nThe Records file has %lu records in it", MaxRecords);
   gap = 2;
   while(MaxRecords/gap > 1000)
      gap *= 2;
   MaxIndex = MaxRecords / gap;
   idx = malloc(MaxIndex * sizeof(i) );

   for(i = 0; i < MaxIndex; i++)  
      idx[i] = 32 * i;
       
   srand(1);    //srand((unsigned) time(&t));    
/*    
   printf("\n\n\n");

   printf("\n Would you like to see the data records [y/n] ? ");
   scanf("%c", &choice);
   if(choice == 'y')  {
      if((pfile=fopen(myfile, "rb")) == NULL)  {
         printf("\nUnable to open %s for writing.\n", myfile);
         abort();
      }

      showIt();
      choice = getchar();
      fclose(pfile);
   }
*/
/*   if((pfile=fopen(myfile, "ab")) == NULL)  {
      printf("\nUnable to open %s for writing.\n", myfile);
      abort();
   }
   while(get_person(pmember))    //as long as we have input
      fwrite(pmember, sizeof member, 1, pfile);  //write it out
   fflush(pfile);
   fclose(pfile);


   if((pfile=fopen(myfile, "rb")) == NULL)  {
      printf("\nUnable to open %s for reading.\n", myfile);
      abort();
   }
*/
//Start your search engines! :)
   
   indxhit = 0;
   start = clock();
   halfgap = gap / 2;
   for(i = 0, gotIt = 0; i < SearchNum; i++)  {
      target = rand() % MaxRecords + 2;  
      if(target >= idx[MaxIndex -1])
         continue;
      //search through the index with a binary search, first
      low = goal = 0; high = MaxIndex;
      while(low <= high)  {
         mid = (low + high) / 2;
         if(target < idx[mid])
            high = mid - 1;
         else if(target > idx[mid])
            low = mid + 1;
         else  {
            goal = 1;  //found it, you're done
            gotIt++;
            indxhit++;
            break;
         }
      }
      if(!goal)  {
         if(target > idx[mid])  {
            if(target > idx[mid] + halfgap) {
               low = idx[mid] + halfgap + 1;
            }
            else  {   //target is <= idx[mid + halfgap]
               low = idx[mid];
            }
         }
         else {   //target < idx[mid] 
            if(target > idx[mid-1] + halfgap) {
               low = idx[mid-1] + halfgap + 1;
            }
            else  {   //target is <= idx[mid] + halfgap
               low = idx[mid-1];
            }
         }
         gotIt += smartIndex(target, low);
      }
   }
   stop = clock();
   printf("\n        Smart Index Search Results: ");
   printf("\n   ============================================== ");
   printf("\n   %lu searches were made", i);
   printf("\n   %lu target record id's were found, ", gotIt);
   printf("in %.2f seconds", (stop - start) / CLK_TCK);
   printf("\n   %lu Index hits were successful", indxhit);   

   rewind(pfile);
   srand(1);                //reset the random number generator
   start = clock();
   for(i = 0, gotIt = 0; i < SearchNum; i++)  {
      target = rand() % MaxRecords + 2;  
      if(target >= idx[MaxIndex -1])
         continue;
      gotIt += binsearch(target, MaxRecords);
   }
   stop = clock();
   printf("\n\n        Plain Binary Search Results: ");
   printf("\n   ============================================== ");
   printf("\n   %lu searches were made", i);
   printf("\n   %lu target record id's were found, ", gotIt);
   printf("in %.2f seconds\n", (stop - start) / CLK_TCK);

   fclose(pfile);
   printf("\n\t\t\t     press enter when ready ");
   getch();

   return 0;
}
/* input function */
int get_person(Customer *temp) {
   static char more = '\0';   //test value for stopping input
   printf("\nDo you want to enter a%s customer [y/n]? ",
   more != '\0'?"nother": "");

   scanf(" %c", &more);
   if(more == 'n') 
      return 0;
   
   printf("\nEnter the ID number for this record: ");
   scanf("%d", &temp->id);
   printf("\nEnter the name of the person: ");
   scanf("%s", temp->name);
   printf("\nEnter %s's state: ", temp->name);
   scanf("%s", temp->state);
   return 1;
}
/* Binary Search function */ 
int binsearch(unsigned long target, unsigned long MaxRecords)  {
   Customer test;
   Customer *ptest = &test;
   fpos_t current = 0;
   unsigned long lo, mid, hi;
   lo = 0;
   hi = MaxRecords - 1;
   rewind(pfile);
   
   while(lo <= hi)  {
     mid = (lo + hi)/2;
     current = mid * sizeof test;
     fsetpos(pfile, &current);    
     fread(ptest, sizeof test, 1, pfile); 
     if(target < ptest->id)
       hi = mid - 1;
     else if(target > ptest->id)
       lo = mid + 1;
     else 
       return 1;
   }
   //printf("\n Target: %lu not found", target);
   return 0;
}
//smart index search
int smartIndex(unsigned long target, unsigned long low)  {
   Customer test;
   Customer *ptest = &test;
   fpos_t current = 0;
   rewind(pfile);

   current = low * sizeof test;

   fsetpos(pfile, &current);    
   fread(ptest, sizeof test, 1, pfile); 
   while(target > ptest->id)  {
      fread(ptest, sizeof test, 1, pfile);
   }
   if(target == ptest->id)
      return 1; //it's a match
   else {  
      // printf("\n Target: %lu not found", target);
      return 0;
   }
}
/* show all records */
void showIt(void)  {
   Customer temp;
   Customer *ptemp = &temp;
   unsigned long i = 0;

   printf("\n\n");
   while(fread(ptemp, sizeof(temp), 1, pfile))  {
      printf("Id: %lu, Name: %s, Company: %s, State: %s\n", 
      ptemp->id, ptemp->name, ptemp->company, ptemp->state);
      ++i;
   }
   printf("\n Complete - there are %lu records\n", i); 
}

Nice work Adak, this is looking like a much nicer experiment. Here's a few more things to consider from a scientific point of view.

1. What's really interesting is the trend, not the average increase at a single data point. If you vary the data size by increasing factors of ten, then graph the results you'll see how each approach grows as a function of data size.

2. In your experiments the keys are unique, what if we want to search over different values (like find all companies with state = "NY"). Now we have to search then scan, which changes the game (Here you'll likely never beat a B+ tree.)

3. The distribution of the data keys in your set-up is uniform (I assume?). This can affect performance. We can try generating random data according to various distributions with various parameters.




PS: I'm not saying you should run out and implement all of this, just something to think about.

Originally Posted by Perspective

Nice work Adak, this is looking like a much nicer experiment. Here's a few more things to consider from a scientific point of view.

1. What's really interesting is the trend, not the average increase at a single data point. If you vary the data size by increasing factors of ten, then graph the results you'll see how each approach grows as a function of data size.

2. In your experiments the keys are unique, what if we want to search over different values (like find all companies with state = "NY"). Now we have to search then scan, which changes the game (Here you'll likely never beat a B+ tree.)

3. The distribution of the data keys in your set-up is uniform (I assume?). This can affect performance. We can try generating random data according to various distributions with various parameters.

PS: I'm not saying you should run out and implement all of this, just something to think about.

I've noticed that the speed increase for the indexed search is quite close, regardless of the number of searches being done in the test. The important factors are the size of the records, and the size of the file.

No, I won't be implementing much more on this program. Main could stand some breaking out into other functions, but I kept them together to make it easy to see that both search modes are being treated the same.

Any search with fast access to data to help guide it will be very competitive, or faster even, than this one. The more info, the better it should be, if it's quickly available.

Yes, these keys are all unique and uniform. Each key would need it's own index file to be used like this. The records would need another member for that index, then say it was for a state, the search would be like:

if(idx[stateIndex[i]] > target) ... where you're not looking at the actual records as they are, but instead, looking at them already sorted, according to their stateIndex value.

That's the beauty of this algorithm. You can index any key, as much as you have RAM for, and any field of the record, can be indexed - not just one. If you want to index every field in the record, and you have the memory for it, you sure can.

Changing distributions of the keys is not a problem, because the "sparse" area's of the index array, will just not be chosen often. The gap would not need to be changed, at all.

Thanks for your interest and suggestions, Perspective.