About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 24 Apr 2007

Simple filesystem file creation benchmark.


See, how broken it is.



It is purely design bug - during directory entry allocation filesystem code runs through all inodes linked into single linked list and checks where is a slot to put a new entry with given size.
This must be dynamic structure like tree/trie, it can not be hash table, since it might be a situation, when there will not be a place to allocate new hash table as contiguous region, and having several layers of hashes is just a one of the trie implementations (judy array or, as I called my implementation, multidimensional trie). Likely B* tree is the best case, but for log-structured filesystem tree structures requrie quite major overhead (not only data block must be copied, but also its parent and so on til root), I need to think about it some more - likely I will introduce defragmentation process involved in writing - i.e. each writes should create new tree, which will store not only modified block, but create bigger contiguous region to store there file/dir content.

But enough empty words for now, I need to make some bits for paid work (which will bring me second monitor, btw, which should allow even more productive work, although not that much I expect) - project should be completed in a week, but I have not yet found a place for second monitor, so I want to complete it today to start complex task of restructuring computers on the table.
Then I will continue to work on my networking trie implementation instead of hash tables - I will just remove all ifdefs and turn trie on unconditionally, after it is ready I plan to complete set of benchmarks to show that it is possible to be faster not only in lookup (where trie is already faster by design), but including the cost of allocation/freeing of the nodes.

/devel/fs :: Link / Comments ()