Printable View
Hi All,
In my C program i am using very large file(approx 400MB) to read parts of it frequently. But due to large file the performance of the program goes down very badly. It shows high I/O usage and I/O wait time.
My question is, What are ways to optimize or tune I/O on linux or how i can get better performance?
I am using
Red Hat Enterprise Linux ES release 4 (Nahant Update 4)
2.6.9-42.EL, x86_64 GNU/Linux
How are you reading the file, and how is the file opened.
Is it a local file, or do you access it over the network?
To me, 400MB is not a huge file (yes, of course, typing 400MB of data in by hand would take a long time [at least if you can't copy'n'paste most of it]). If you have a few gigabytes of memory, it should be possible to cache that file (or the regions that are frequently accessed at least).
--
Mats
reading the file with read function.
Actually the files are of database. One file is there which keeps the index information and based on the index (Using binary search method to search index with the help of key value) data is fetched from data file.
Size of index file is around 100 MB and size of data file is around 300 MB.
Yes it is a local file.
When i see there is high I/O wait then reading goes damn slow. Is there any way through which i can prevent I/O(swap In/Out) for these files. Or tune my machine?
read() or fread()?
How do you open the file? (fopen() or open(), and what arguments?)
Is there only one process accessing the file, or many processes?
Are you mixing reads and writes, or only doing reads?
Do you open & close the file for each request, or is there "one open at start of day, and close at end of day"?
If you have enough free memory in the system, it should automatically cache the file, unless you have specifically requested it should NOT.
--
Mats
Hardware speed up's include:
1) Use a RAID drive configuration
2) Have the data on a physically separate HD from the system files.
3) Use a faster drive for the data drive - SSD if you can justify the expense
Software:
1) Use fread() in the natural big chunk size that matches well with the architecture of
that particular system.
2) Don't use linked lists or other largely sequential data structures- use arrays, instead.
3) Use malloc and slower functions (strcmp, strlen, sizeof, etc. sqrt), as little as possible
4) Keep your data that you're processing, together, together in your program. Locality of reference, is critical to avoid flushing the cache memory.
5) Look to your algorithms - that's the biggest improvement you can make, if it's non-optimal. Don't optimize the code, before the algorithm is really right.
6) Profile and test the program and functions therein. Any program that has a lot of I/O is likely to have the I/O as the bottleneck. So when you are reading data, read big chunks of it, when you're writing data, again - big chunks. Hopefully, again on separate physical HD's (not just different logical drives).
The worst thing is to have read 100 bytes here, write 50 bytes over here, and the other 50 bytes in another file, over there, then reading another 100 bytes, especially on the same physical hard drive.
A recent program of mine processes 75,000 records, in two data files of 28 Megs, including a multi-level merge of some 7,400 records. For the various sorting, I thought I'd use Quicksort from the C standard library.
Because the sorting is in small classification groups, Quicksort was slower than a bubblesort, in my tests. <shock> I love Quicksort, but for small groups it can't match selection or bubblesort. (no, the data was not partially sorted)
The reason, and the reason that program is finished in about 5 seconds, is because it takes full advantage of the HD buffer and arrays. Big reads, big writes, and it uses fscanf() for much of the data input into the array of structs. Way faster than fgets(), or something like that.
You may want to check your HD also, and just see that in fact, it's giving you the sustained throughput that it should be. Case in point, I recently had to back up an entire HD, so I hooked it up to the mobo, using the ATA cable going to/from the optical drive. The HD's were identical in size and make, with a large disk buffer.
The data *crawled*, from one drive to the other! :( The reason was the backup HD had been connected to the slave connector of the ATA cable, and it was set for the slowest device on the ATA cable - an 8X optical drive. Incredibly slow! I haven't seen a HD move data that slow since x86-80286 cpu days.
Another factor was that these HD's apparently use their large disk buffer to act like they have a fine throughput rate. Once you're past the data in the buffer, it's *much* slower.
Good luck, sorry to make this so long.
You might want to check also the place of your files.
Make sure that all files that are frecuently read are in the same place. Not only in the same HD, I would put them in the same folder. And if you can next to the executable.
Also ... it depends on your algorithm but, Maybe you should consider using fseek() or equivalents to go to the exact position of your file. I think fseek is a little bit faster.
Since when is sizeof slow? And since when is it a function? ;)Quote:
Originally Posted by Adak
Placement on hard-disk and location in relation to the executable is unlikely to affect thing if the files involved are 400MB worth of data.Quote:
Originally Posted by nacho4d
Adak makes several good suggestions, although only some of them deal with I/O optimization.
--
Mats
Maven, there is a much faster way (possibly - depends on your data), to do your search, than to use the nice binary search technique.
I'm a big fan of binary search, but I have seen a better technique, also. Actually, I was on the losing end of a debate on what was the fastest searcher, so I tested it myself.
If you send me a link to some representative data, I'll see if this indexing search can work faster for you, as well.
It can be *much* faster, but that depends on the data and how this index can be smartly built for that data.
Do you read at least the index file in only once and hold it in RAM? 100MB isn't that much.Quote:
Originally Posted by maven
Have you considered using a B-Tree instead of a binary tree? These are what directory structures use because they minimise the number of disk accesses or updates required.
Is the data or index file something that would compress easily? If you can even halve the space of the data or index file you could significantly reduce the IO.
If you dont want to hold the whole 400MB in RAM at once, how about having a cache of say the 10 most recently accessed chunks of the file? Even caching 5% of it could make a huge difference depending on data access patterns.
Finally, have you considered memory-mapped IO?
Hey -- just a shot in the dark, but since this is linux/GNU: if the file size is fairly constant you could mmap()
Whether it's mmap()'d or not, the kernel should be trying to cache as many file blocks as possible.Quote:
Originally Posted by MK27
Sequentially reading from a file should be fast, unless the filesystem is totally fragmented. I suspect the problem comes from seeking like crazy. If you have a gig of RAM, then the whole file might end up in cache, but if you have considerably less than that, seeking is going to create a serious hit, no matter how you access the file.
Right...a file in RAM is a file in RAM. Just ignore me ;)Quote:
Originally Posted by brewbuck
Well it does make a difference, just not one that I think would be significant to performance. When a file is read normally, the blocks are cached in the "buffer cache." If the file is mmap()'d, the blocks are cached in the page cache, and associated with the file through backing store. So the specific cache which is used is different, but it would be a bug if the performance was signficantly different.Quote:
Originally Posted by MK27
Binary search on disk is very slow. In many cases, a linear scan of your data may be faster than binary search. Disk drives are fast for sequential reads and slow for random access. Binary search has way too much random access for disk based algorithms.
400mb is tiny, buffer it in memory.
All,
Thanks a lot for your valuable suggestion.
i am using open call with O_RDWR mode. and using lseek to locate the offset.
According to the behavior of process i feel that problem is file system caching/paging. The first time the program is run it takes far longer to execute than any subsequent runs.
Is there any way to by-pass the file system caching, or something like direct I/O for redhat linux machine??
Files that are frequently read are under the same directory.
My data is in very simple format.
for example.
2334312,543,MYNAME,NYC,20090302
here 2334312 is the key value which is unique. like so data file contains around 5 millions of data and index file contains index information for these 5 million data.
Note: Currently I am performing only read on this file and only one process is accessing it.
This seems like a strange theory. First you say that it seems faster once it's cached, then you ask how to disable caching? (The reason it's fast after the first run is because it's been cached)Quote:
Originally Posted by maven
To prove/disprove my idea, you can disable caching on the file by opening it in uncached mode using O_DIRECT.
But it is not always in cache. As i have said it earlier that i am seeing high I/O.
I have heared that not all that many platforms support Direct I/O. So it will be of no use by forcing it to open with O_DIRECT mode. I am using processor AMD Opteron(tm) Processor 246.
I have tried it to open with O_DIRECT mode. but perfomance was the same.
Clearly, you *want* the data indexed - definitely!
"Perspective" posted up a fact that should be explored further:
HD's are *very* fast for sequential reading, and *very* slow for random access reading. Which brings up the idea of just adding a HD controller with a large amount of RAM, to extend the amount of data that the HD has "at it's fingertips", and can access without any further disk reading.
I recall the distinct pleasure of installing one in my PC many years ago - suddenly my PC was on steroids for disk I/O! :)
If time is money, I'd say this could be your most cost-effective and quickest solution.
Next is the search. I mentioned previously that a binary search was not the fastest, even in RAM. On a HD, it's even slower, because of the distances the read head has to travel.
Here's some more details:
I took 3,000 records into an array, and used two searching techniques, binary and smart indexing. Then I did 100,000 lookup's of those records, randomly chosen, and timed how long it took each type of search to finish the 100k lookups.
Smart index was 5 X faster than binary searching.
It worked like this:
The database was indexed so the middle record ID of each part was then used as the "starting point" for any search in it's own section. (sort of like the mid point of a binary search).
Now the closest index ID start point was found, in your case, the right offset to the best starting point, would be known. Starting with that indexed record, the program would search up or down, sequentially, until it found it's proper record.
I suppose you're thinking "That can't be faster than binary search". That's what I thought, as well. But it is, and it can be fine-tuned to add even better performance, if you program in more "granularity" into the indexing part of it.
It can make MORE comparisons than a binary search, on average, but those comparisons are with records being read in *sequentially* from the HD, (and thus probably already in the buffer), rather than the schizoid HD reads needed by the binary search algorithm.
Even in an array, the indexed search was 500% faster. You couldn't tell it by just one search though - they were just too fast. But give it 100,000 searches, and the difference was immediately noticeable.
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.
How much memory does the machine have? If you have more than 1GB of RAM, then you should be able to simply load the entire index table into memory, and use it from there [or at least use a mechanism of storing the last 2-300 entries. Since your binary search will jump all over the place, but some elements will be COMMON in that list, keeping those in RAM will speed things up A LOT.
Actually, the fact that tmpfs works for you means that you have enough memory to load all the data into RAM - you may not need to load it ALL at once, but basically, once it's been read in, keep it in memory. It should speed things up (probably MORE than the 10x you get from tmpfs, since you do not need to copy the data as many times as the read() system call would do).
The fact that O_DIRECT is showing no difference tells me that caching is not working for you (but also not hindering anything).
--
Mats
how to do "simply load the entire index table into memory". and will it gurantees that if some other memory consuming process will come than index table will not be swapped out?
Are you REALLY not having enough memory? Your tmpfs test seems to suggest that you DO have enough memory.Quote:
Originally Posted by maven
But of course, if you intend to run MANY copies of the application, you may need to use some more convoluted method (e.g. using shared memory, mmap() or some such).
--
Mats
Yes system has enough memory, i have stopped some meory consuming processes for the time being thats why for the time i have this much memory.
One thing i am not able to understand if program is able to work great with tmpfs then why it is not giving performance when other process are stopped and system has enough memory? And while working with tmpfs I/O wait is negligible where as without tmpfs it is 98% average.
Ok, let's get one thing very clear: If you do not have enough memory SOMETHING has to be swapped to disk at some point.Quote:
Originally Posted by maven
But if you are frequently accessing your index table, then it should not be what gets swapped out. Some other memory consuming process that isn't very active will get thrown out [most likely].
Second, I'm pretty sure you hit the same records A LOT in your binary search of the index. So caching THOSE entries would help a whole lot - knowing which they are is the hard part if the data involved [either what you search for, or what you search in] changes.
One thing to experiment with would be to put only the index in tmpfs and keep the data file itself on hard-disk. Does that give a 10% or 50% or 8x speed up?
I have experimented it. And it gave good perfomance as well. As said 8x.
what we can conclude now?
Keep frequently accessed meta-data on the VM based tmpfs while keeping the data itself on the disk device; see here for details.
1) static RAM is many times faster than getting data from a HD. Same with HD buffer and HD controller RAM. They fly. If you're not using a HD controller with a large buffer, you might want to look into that. :)Quote:
Originally Posted by maven
2) For any data in RAM that changes, be sure to keep your data updated frequently, on the HD. Power outages and such, will occur. A battery back up for the system, might be wise. Give you time to save the current updated data and shut down, at least.
3) Sequential reads are much faster than random reads on a HD. This doesn't hold for SSD drives, because they're basically RAM.
My old smart index program bit the dust when the disk was seriously infected despite a good AV program and firewall, so I'm working on a new program to show how a smart indexer can blow the doors off a binary search.
Cheers for now.
Can you give some links where i can find the concept of smart index?
No, I can't. I was in the Yahoo C programming group, and mentioned how much I liked binary search, and the mod said "Not as fast in this case". Then he starts a little BigO(n), and O(log n) stuff and my eyes just started glazing over.Quote:
Originally Posted by maven
So I challenged him to a test - and his way (smart indexing) was indeed quite a bit faster, but you couldn't tell it from a small test, you had to loop searches thousands of time before any run time could be found, at all.
In the final test I made with (iirc), a 100,000 searches, smart indexing was anywhere from 200% to 700% percent faster, depending on the specifics.
I spent some time googling for it, but I couldn't find anything exactly on it.
As mentioned above, my test program was lost in a horrendous virus attack on that system.
I remember the gist of the program, and have prepared an even better test for it. A file of 500 records, for the disk has been made up. The program automatically builds the indexes, and has the binary search function done, as well.
It will roughly be done later today, but I may need another day to get some testing done.
I want it to be a fair test of the two algorithms.
See you then.
Guys, keeping index only at tmpfs doesnt work to give 8x performnace. It is normal as 1X only. I looked it wrong.Quote:
Originally Posted by maven
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.Quote:
Originally Posted by maven
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
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?Quote:
Originally Posted by maven
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
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.Quote:
Originally Posted by brewbuck
--
Mats
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.Quote:
Originally Posted by iMalc
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:
The RAM table, is the index. They use an Indexed or Smart Binary, search.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 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? :p
R/L has unfortunately insinuated itself into my programming time, but I'll throw up something when I get some time.
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:
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.Code:struct records {
unsigned long id;
char name[20];
char state[20];
}
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.
The unsigned long int's are there because I wanted to make this program as robust for a large data file, as possible.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, ¤t);
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, ¤t);
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);
}
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.
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, ¤t);
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, ¤t);
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.
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.Quote:
Originally Posted by Perspective
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.