Home | Blog | Software | Reviews and Features | Forum | Help | Donate | About us
topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • December 04, 2016, 08:18:46 AM
  • Proudly celebrating 10 years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Last post Author Topic: Use video RAM as a swap disk?  (Read 14506 times)

Ralf Maximus

  • Supporting Member
  • Joined in 2007
  • **
  • Posts: 927
    • View Profile
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #25 on: October 15, 2007, 09:12:33 AM »
Quote
The number of files in a single dataset can get up to several 100.000 entries. Big networks could deliver several millions.

How many searchable bytes per entry?  100?  1000?  100 * 2M = 200 megabytes, still within the realm of keeping all the indexes within system RAM.  The best way to optimize disk I/O is to avoid it. :-)

Stop me if you've heard this before, but optimization in and of itself is a game of diminishing returns.  You can spend hours shaving tenths of a second off a routine -- is it worth it?  Maybe, if that code is run inside an inner loop.  But knowing WHERE to optimize is most of the trick.

Personally I'd look at trying to pre-identify which data is most likely to be needed most often.  Using some kind of date parameter can be helpful in some cases, like a movie database.  Prioritize newer movies/entries so their indexes stay in RAM, move the older stuff to the disk-bound indexes.

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,029
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #26 on: October 15, 2007, 09:15:31 AM »
I have something like the following in mind - 48 bytes on an x86-32 machine with default padding, 72 bytes for x86-64. Which means you could keep the main structures in-memory for 1 million files and only use 48 megabytes of memory, not bad for speed.

And since it's a fixed-size structure, it would be very easy and efficient to do read caching and only keep part of the structure in memory. Having stringtable index for both the "real" path/file string as well as uppercase versions means that if you're searching for a non-wildcard string or checking if a file already exists, you're only doing an integer operation instead of a (relatively :) )slow string compare. Here's my idea of a fileobject structure:

Code: C++ [Select]
  1. struct FileObject
  2. {
  3.         uint32          strPath;                // stringtable index of pathname (containing folder)
  4.         uint32          strPathUp;              // -"-, uppercase version
  5.         uint32          strName;                // stringtable index of filename
  6.         uint32          strNameUp;              // -"-, uppercase version
  7.  
  8.         uint64          fileSize;
  9.         uint32          fileFlags;              // flags & attributes
  10.         FILETIME        timeCreate;             // file creation time
  11.         FILETIME        timeUpdate;             // file last update time
  12.  
  13.         uint32          blobIndex;              // "blob" table index (plugin data)
  14. };


The string table requires some more explanation, in order to see why it's a good idea. Unique strings are only to be stored once, so identically named files have the same index (fast compares, as mentioned earlier). The string data can be cached as well, so you don't have to keep it all in memory. String indexes are static (ie., adding a new string doesn't cause other string indexes to change) - but at the same time we really want the string to be sorted, to have fast lookups. We want to be able to use binary searches.

So, the string table consists of a "string index table" that maps string indexes as used in the FileObject to the sorted indexes (which will change upon adding a string). Other than that, the stringtable consists of {u32 size, u32 filepos} pairs (or u64 if you want to support really huge systems). So, you can keep the entire stringtable index tables in memory, or (again since it's a fixed-size structure) you can do fast & efficient lookups - the index tables as well as the strings themselves can be cached.

Strings and uppercase strings could be in two separate tables, or share one table.

So, if you're doing a non-wildcard search, you start by uppercasing the search string, and then check if it's present in the uppercase string table. If not, you can abort your search right away. If it's present, the lookup gives you an integer for your comparisons, and you can then do ultra-fast binary search for the file. Wildcard searches require somewhat more work, but still not that bad, if you implement caching properly.

The blob table would take some pondering, since it has more variable-length stuff. I'm a big fan of "top-level fixed-size structures" because it makes things easier and more efficient, at the cost of some additional indirection...

Code: C++ [Select]
  1. struct BlobIndex
  2. {
  3.         u32             blobCount;      // *number* of blob items for this index
  4.         u64             fileOffset;     // file position of BlobItem list
  5. };
  6.  
  7. struct BlobItem
  8. {
  9.         GUID    blobType;       // blob type - I prefer GUIDs to ints
  10.         u32             blobSize;       // size of the blob item
  11.         u64             fileOffset;     // file position of the blob data
  12. };

Again, the main structure (array of BlobIndex'es) is small and you can keep a lot of them in memory without problems, and it's easy to cache as well because of the fixed size. It's also fairly fast to get the list of blob items, since it's just seeking to bidx.fileOffset and reading blobCount*sizeof(BlobItem) bytes.

With this approach, and proper serilization, you can eliminate the "write-seekback-updatewrite-seekend" entirely, you don't have to do a "read-seek" loop just to get your lists, etc.

Even for 100.000's of files you could keep the entire main structures in memory without being too much of a memory hog (speed often comes at a size penalty though), but it would still be very easy to do caching if your class layout is decent.

It would be relatively trivial to code as well, I think the "worst" code to write would be updating the string-index table upon sorting, but that's really not too bad. Binary search of strings, as well as stringcompare-by-integercheck means very nice speed properties.

Also, with proper class design, it's also very easy to do performance/stats collecting, which you can use to tune things like cache sizes... either by manual analyzing, or adapting at runtime.

If you want full-text searching in files, that could probably be added as a blob item, although I think I'd prefer an additional file for that.
- carpe noctem

Crush

  • Member
  • Joined in 2006
  • **
  • Posts: 399
  • Hello dude!
    • View Profile
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #27 on: October 15, 2007, 03:01:09 PM »
Hi, the coders are waking up now  :P ?
We left the theme of this thread by far I think. Perhaps we should open a new "coders" corner?

Thank U very much for so many hints and tricks. I really welcome each suggestion to improve the program and will think about it.

@Ralf Maximus
I was calculating the average by characters/enties of my HD content about 202 characters per entry - other not deep structures file-systems shouldn´t have this size. Perhaps between 50-100, I guess. Your´re right. I heard your optimisation clue very often before. I have enough experience to know where to look at to release real power.
The system is planned to be as flexible as possible. It should be possible to create special search databases containing only these informations you really want to look at or need. If you don´t like to have mp3 previews or big thumnails (only a special/maximum size) you should be able to create a database that contains only your entries, so that other unneeded datas don´t block space on your HD. This way makes it possible to create mini-databases that contains all you like on a very small USB-Stick for example. Only the main search-header will be the same. I also want to include hit-counters of previous often result-serving catalogs to optimize filecaching.

@F0dder
I often was told by "users" speed is not very important. I tried a lot of programs (see my big list) and found 99% of them not managing my personal needs. Nearly all preload the catalogs totally in memory, searching several catalogs without preloading them is not possible and self optimizing searches are non-existant. There are some heavy code-dependant-slowdowns and I would say every search, that needs more than 10-20 seconds is by far too long. I wanted to find a pretty smart way to offer speed and functionality, prefering speed myself. At the moment I can get about 40-50 million entries case independant searched with results on my rather slow and old laptop calculating the strings show a case independant substring search-power of 970.000.000 characters/second (ok, at the moment only ASCII - Unicode is also planned). So I can say it can exmine at least 2.000.000.000 chars/second with storing the results (with a quite old 3.2Ghz CPU). Others things like analyzing previous searches and building specialized speedup-hashtables will make another big performance explosion, I think. This is only for additional information of the momentary state. This search speed makes totally realtime searches while typing possible. Searching through my 60 GB HD with ~215.942 entries is ready in 4-5 milliseconds  :Thmbsup:!

I also thought about using pointers to the strings. There are several reasons why I don´t want to do this:
1.) Showing/Calculation directory structures need an intensive analysis of the full index
2.) You need a second file for effective adding new entries to the database and opening/closing files need much more time than packing all into one. Seeks are about 250-400 times faster than open/close commands (I also benched things like this :D).
3.) Such a sorted structure is only senseful for a perfect match search. You achieve even higher speeds with temporary hashtables. If I would do something similar I would prefer a radixtable.
4.) I only made this speed by implementing some special hashes in the mainblock of the entry. So I only have to test a rather small bunch of strings by comparisons and this I do with an ultra-fast selfmade Boyer-Moore-Crush :P search that - because of its algorithm - doesn´t needs to convert characters to upper/lower case to check them for a substring. So it´s no need to store normal & uppercase strings.
5.) Most searches normal people are starting are substring searches and no perfect matches - and this I do extremly fast. Therefore I also want to implement fuzzy-searches. For the few perfect-match searches I can create the temporary hashmap. Often you know the type/ending of strings (.dll/.exe/.doc or combinations of several like this) and this also needs a special treatment for faster access. The same has to be done for filters/triggers/aliases and so on.

The path is stored some entries before and, if it would really be needed, I could insert perhaps a reference to it. But each byte more slows down the memory-friendly search. If there is the need to sort the entries I will do it in extra tables on the fly.

I agree with "top-level fixed-size structures" (entering the club).

Regarding to your Indexing-System I´d like to say that all objects are managed by a reference-system. You can point to the file/fileposition, the memory with a single entry or at the full cached index with offset - different treatments needs different managing types.

Sorting would destroy some features as adding changes with time stamps. To access the entries with the right time would need a total reorganisation of the sorting. This also made the decision easier to do sorting with extra tables.

Performance/stats collecting is already planned.

The writecaching also was to write the results or their references as fast as possible to collect previous searches that you can call/analyze/compare against if needed. So your memory-usage can be minimized to nearly nothing.

Besides, my Filesystem-benching also helped to find a new way to scan directory structures on medias much faster then the "normal" way.

Perhaps I can use the binary search in another way as you ment - I´ll think about it. Some different search algos I was thinking of is bloomsearching,  multistring-searches and heuristic searching for similarities. The more different searchtypes I implement, the more I feel free for searching.
« Last Edit: October 15, 2007, 03:03:11 PM by Crush »

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,029
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #28 on: October 15, 2007, 03:20:05 PM »
Quote from: Crush
We left the theme of this thread by far I think. Perhaps we should open a new "coders" corner?
We should have a moderator move all filesearchindexing stuff to a different thread :)

I agree that people are normally interested in fuzzy and not exact matches, I still can't help loving the simplicity & speed of "compare two strings just by comparing two integers" :)

About open/close speed, I'd keep the relevant files open for the duration of the program, usually you're going to do multiple searches (at least I tend to) - and there's not much reason not to keep them open.

Case-insensitive boyer-moore is cute, and a decent approach when you're doing partial searches without wildcards - I would definitely do search term analysis and choose method depending on that.

I still think the stringtable is a good idea, since it simplifies the main structures so much - and with caching, it should become very efficient as well.

Quote from: Crush
Sorting would destroy some features as adding changes with time stamps. To access the entries with the right time would need a total reorganisation of the sorting. This also made the decision easier to do sorting with extra tables.
Well, the sorting was only for the stringtable really, and only to make inserts and lookups very fast (fast exact lookups are useful not just for exact matches, but also when adding new (possibly already existing) strings to the stringtable).

Sorting your filelists based on different criteria should indeed be done by creating an additional vector of pointers/indexes and sort those, leaving the original structures intact. Much faster than swapping around, too.

Quote from: Crush
Besides, my Filesystem-benching also helped to find a new way to scan directory structures on medias much faster then the "normal" way.
Do tell :)

I was playing around with a FindFirstFile/FindNextFile loop that didn't SetCurrentDirectory(), didn't recurse, and used a single MAX_PATH char array... but I realized that FindFirstFile internally does a SetCurrentDirectory(), so you don't save much by doing it this way, apart from some limited amount of stack memory.

bloomsearching?
- carpe noctem

Crush

  • Member
  • Joined in 2006
  • **
  • Posts: 399
  • Hello dude!
    • View Profile
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #29 on: October 15, 2007, 04:37:18 PM »
It´s too simple and if you didn´t recursed you made all right! Changing the directories with FindFile() needs much more time than FindNextFile(). That´s all to know. So you step through all members of the actual directory and remember all Dir-entries in a search-array (you later look at their content). Then you do the same with all members within the array. That´s much faster than the iterative way if you find a directory. But this has a disadvantage: The calculation of the dir-sizes is more complicate.

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,029
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #30 on: October 15, 2007, 06:19:51 PM »
Ah, makes sense - and shouldn't be too bad to code, although it would be a bit more complicated and require a bit more memory (ie., storing list of folders-to-check-later rather than processing when you find them).

Calculation of dirsizes shouldn't be too bad, a simplistic approach would be walking the tree after you're done.

Heh, I really feel like resuming work on my own file indexer now :)
- carpe noctem

Crush

  • Member
  • Joined in 2006
  • **
  • Posts: 399
  • Hello dude!
    • View Profile
    • Read more about this member.
    • Donate to Member
Re: Use video RAM as a swap disk?
« Reply #31 on: October 16, 2007, 01:59:22 AM »
Aha, I´m not alone with my kind of project... cool ... I think this is a really useful type of software. It´s a pity that there have been quite less suggestions in my what-do-you-like-to-see-threads (not only at Donationcoder).

I spent very much time in trying out different approaches to maximum performance and analysis of existing/benching catalogers, code and Filesystems. There are also other screws to turn: Perhaps there are ways to make the structure even more flexible than normal a fixed structure. I´ve already experimented with some emulation-like dynamic recompiler that creates code from snippets, treating only these datas and parameters you really need, skipping unnecessary code like date/time/dir checking if not used for searches. I´m only thinking about how to use this in a simple way with different structures (especially for additional outsourced datas). A main reason of the design is to use several cpu-cores parallel that they even can do different search tasks returning different result lists and that the code could be used for other types of high speed/much information databases or also simple ones (movie, library, customer management and so on). To organize this and other planned features working optimal together also crushes my brain.