Performance issue!

This is a discussion on Performance issue! within the C Programming forums, part of the General Programming Boards category; Originally Posted by maven I have experimented it. And it gave good perfomance as well. As said 8x. Guys, keeping ...

  1. #31
    Registered User
    Join Date
    Dec 2005
    Posts
    134
    Quote Originally Posted by maven View Post
    I have experimented it. And it gave good perfomance as well. As said 8x.
    Guys, keeping index only at tmpfs doesnt work to give 8x performnace. It is normal as 1X only. I looked it wrong.
    It means when both files are on tmpfs then only it is able to give great performance.
    S_ccess is waiting for u. Go Ahead, put u there.

  2. #32
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by maven View Post
    Guys, keeping index only at tmpfs doesnt work to give 8x performnace. It is normal as 1X only. I looked it wrong.
    It means when both files are on tmpfs then only it is able to give great performance.
    That doesn't make much sense to me.

    If you are doing a binary search, I expect that you will be benefiting mainly from the index file being on the tmpfs, and very little from the data itself - at 5M entries, you will be doing 22-23 reads on the index table for every read of the actual data, which makes it unlikely that you will see much benefit for the 1 in 20 reads, and a good benefit from the 19 in 20 reads.

    Considering that the data-file is only about 3x the size of the index table, I'd expect there to not be a VERY large difference from having the data file on the tmpfs.

    This may be a sign that your index file is being cached as expected, and that the data file [which I expect doesn't have many repeat hits to the same place anyways] is the bottleneck.

    You may want to instrument your code with RDTSC (http://en.wikipedia.org/wiki/Time_Stamp_Counter) to figure out where your time is being spent. I'd do that with uni-processor (reboot the machine with SMP turned off), so that you avoid the problems of TSC running differently on the two machines. [Either that, or filter out spuriously large/small/negative values].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #33
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by maven View Post
    Definately i will try to change my secrah technique to Smart index . Can you please give some links for some help on Smart index?

    One thing i have tested and found a huge difference in lookup performance.
    i have mouted the directory as tmpfs(It is a temporary ram based file system). And it showed consistent performance with 10 X speed.
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #34
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    iMalc makes a good point. But I think it's also important to understand where in your code the time is spent. If there is no speed improvement from moving the index to tmpfs, it's likely that not a lot of your IO-wait time is spent in the searching function.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #35
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Another possibility is to block-compress your index file. With CPU speeds being what they are, some compression algorithms can actually decompress faster than the raw read rate off the disk. So you can actually go faster by reading compressed data and then decompressing it.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #36
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    Another possibility is to block-compress your index file. With CPU speeds being what they are, some compression algorithms can actually decompress faster than the raw read rate off the disk. So you can actually go faster by reading compressed data and then decompressing it.
    Except I still think it's the "main" file that takes time to read - at least if we believe the latest post by original poster.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #37
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by iMalc View Post
    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.

  8. #38
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a basic example of a smart index search program. The file being searched consists of just this struct, for each of the 100 records:

    Code:
    struct records  {
       unsigned long id;                     
       char name[20];
       char state[20];
    }
    The smart index search averages 391% faster, where a large number of searches are required - I chose 100,000, 200,000, 300,000, and 500,000 as my testing search numbers.

    Further speed-ups for the smart index algorithm consist of things like adding a 5 member struct into each index array subscript, then adding the logic to further break down the range of records that must be searched by the hard drive.

    I added a 4% wrong record number search, just for fun - it made no difference, since both searches continue past them, immediately.

    You can use the index logic with a binary search, sending the binsearch() function the closer low and high range values that the index will always provide.

    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 MaxRecords 100  
    #define MaxIndex 6
    #define SearchNum 100000
    
    char myfile[] = "C:\\myfile.bin";
    FILE *pfile = NULL;
    
    typedef struct customer {
       unsigned long id;
       char name[20];
       char state[20];
    }Customer;
    
    int get_person(Customer *pcustomer);  //input
    void showIt(void);                //show all records
    int binsearch(unsigned long target);        //binary search for target id
    int smartIndex(unsigned long target, unsigned long low);  
    
    int main(void) {
       clock_t start, stop;
       time_t t;
       int goal;   
       unsigned long i, gotIt, searches, target, low, mid, high, indxhit;
       char choice;
       Customer member;  //declares a customer struct
       Customer *pmember = &member;  //ptr to the customer member
       int idx[MaxIndex] = { 0, 20, 40, 60, 80, 100 };
    
       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 writing.\n", myfile);
          abort();
       }
       
       indxhit = 0;
       start = clock();
       for(i = 0, gotIt = 0; i < SearchNum; i++)  {
          target = rand() % MaxRecords + 4;  
          if(target >= idx[MaxIndex -1])
             continue;
          //search through the index with a binary search, first
          low = goal = 0; high = MaxIndex - 1;
          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] + 10) {
                   low = idx[mid] + 11;
                }
                else  {   //target is <= idx[mid + 10]
                   low = idx[mid];
                }
             }
             else {   //target < idx[mid] 
                if(target > idx[mid-1] + 10) {
                   low = idx[mid-1] + 11;
                }
                else  {   //target is <= idx[mid] + 10
                   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);
       start = clock();
       for(i = 0, gotIt = 0; i < SearchNum; i++)  {
          target = rand() % MaxRecords + 4;  
          if(target >= idx[MaxIndex -1])
             continue;
          gotIt += binsearch(target);
       }
       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 details of a%s person [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)  {
       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: %d 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: %d not found", target);
          return 0;
       }
    }
    /* show all records */
    void showIt(void)  {
       Customer temp;
       Customer *ptemp = &temp;
       int i = 0;
    
       printf("\n\n");
       while(fread(ptemp, sizeof(temp), 1, pfile))  {
          printf("Id: %d, Name: %s, State: %s\n", 
          ptemp->id, ptemp->name, ptemp->state);
          ++i;
       }
       printf("\n Complete - there are %d records\n", i); 
    }
    The unsigned long int's are there because I wanted to make this program as robust for a large data file, as possible.

    Is this over-hyped? No. It's 390% faster. Is it "third hand knowledge"? No.

    It also hasn't been thoroughly tested, so be sure to do your own, if you decide to use it someplace.
    Attached Images Attached Images  
    Last edited by Adak; 03-21-2009 at 08:55 PM.

  9. #39
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  10. #40
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  11. #41
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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); 
    }
    Attached Images Attached Images  

  12. #42
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  13. #43
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Perspective View Post
    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.

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. float calculation issue
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 05-26-2008, 04:56 AM
  2. Performance and footprint of virtual function
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-31-2008, 06:34 PM
  3. File map performance
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-04-2008, 03:18 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. inheritance and performance
    By kuhnmi in forum C++ Programming
    Replies: 5
    Last Post: 08-04-2004, 12:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21