At 3:30 PM +0200 on 7/22/99, M. Uli Kusterer wrote:
>>I bet I can write a faster block file system :)
>
>Anthony,
>
> why don't you tell me what slow techniques I'm using and how to replace
>them with faster ones? This would maybe now take more time, but as I'd
>learn techniques to speed up my programs, my future code for OpenCard would
>be as fast as yours, and then we'd have two people writing fast code, and
>not just one. After all, Open Source doesn't mean just giving away code --
>it means sharing code, work force, etc.
Well, my first suggestion would be not to do a linear search for free
space. Keep all the free blocks in a balanced tree, sorted by size. You can
then quickly search for a block of the propper size. And if the search is
still too slow, though it won't be, do some hash-tabling to find a start
point in the tree.
Adjacent free blocks should be combined into a single free block.
Optimize it as we'll need it: Getting objects of the current card (or
background) should be fast, and should not require searching through all of
the objects of that type. It should also be fast to iterate through all
objects. And lookup by name, id, and number must also be fast.
Profile the thing with a LOT of blocks (say, 100,000 -- a million would be
better), doing random operations with blocks of random size, and not
compacting often, and see where the time is spent. Focus on those parts
first. I've suggested the above because I'm fairly sure you're going to be
spending lots of time with free-block searches.
Also, if the file is small, read the whole thing in. It's silly to be
paging a 80K file, for example. On some OS's, it won't matter (Linux, for
example), because they do real disk caching -- and have fast calls. But on
the MacOS, it does.
Ever wondered why you can insert a character before three megs of
characters in a word processor and not deal with waiting for it to
reallocate and move three megs of data? Because it, like I hope you'd do,
is willing to fragment things. It cleans up at idle time. Something like
this can be done for streamed blocks:
take:
BLOCK[]
0 => "Hello, world! This is a large string, full of about
30 "
"megabytes of text...."
insert "cruel " after "Hello, " gives
BLOCK[]
0 => "Hello, cruel "
1 => "world! This is a large string, full of about 30"
" megabytes of text...."
Which copied all of 20 or so bytes, instead of 30MB. Of course, the
same can be done for removal, as well, except that copies no bytes.
I should wanr that this requires serious memory management work: No block
is guaranteed to be a valid pointer to pass to delete, and a few blocks may
share the same pointer. You must clean the mess up at idle time, though, or
it quickly grows beyond control. Also, you should not fragment small things
-- it's quicker to copy them.
Also, if someone starts streeming to a new block (or a small block), you
could ask for an "expected final size" and place it somewhere where that
much room is availible -- at the end of the file, for example.
I hope I've given you enough ideas to keep you busy until ResCraft is out :)
