Re: Yet another take on ppfDirTree

[Christian Reiniger <warewolf@mayn.de>]

Bjarke Hammersholt Roune wrote:

>>I don't think arrays would be good. The dynamic sizing of lists makes
>>things effectively simpler.
>>
>You can resize arrays too... I do see how it wouldn't be a good idea ,
>though, if you don't store the hash-table as a hash-table, but just as a big
>bunch of entries.
>
>Write a class for these arrays if you're afraid of complexity. That way, you
>can't honestly mean that using an array is so mind-boggingly difficult and
>complex that its unviable... Its something that everybody have done 100s of
>times. Well, ok, atleast I have. I don't see how a programmer could get
>around using and resizing arrays in the course of a career, nomatter how
>short-lived.

Well, but resizing arrays is expensive. Wait - actually it isnt, I mean, it
*is* expensive but we don't have to do it ;)
The nice thing is that (for Format 0 Paks, i.e. the only place where the
hash construction speed really matters) we know exactly how many entries
the hash (in total) will have. That means we can just allocate an array for
all these entries and (given that the entries are stored in the Pak sorted
by hash key, which is only natural) we can just use an algo like that:

EntryArray = new Entry [count]; // the array holding all entries
Hashtable = new  Entry* [HTSize]; // hash table

// init hash table etc

int HashChainStart = 0;
int HashChainEnd   = 0;
int CurrentHashKey = 0;

for (entry = ReadEntry ())
{
  if (entry.GetKey () == CurrentHashKey) 
  {  
    EntryArray [HashChainEnd] = entry;
    HashChainEnd++;
  }
  else
  {
    Hashtable [CurrentHashKey].SetArraySize (HashChainEnd - HashChainStart);
    HashChainStart = HashChainEnd;
    CurrentHashKey = entry.GetKey ();
    Hashtable [CurrentHashKey].SetArrayStart (&EntryArray[HashChainStart]);
    EntryArray [HashChainEnd] = entry;
    HashChainEnd++;
  }
}


Or to illustrate it, say we have an hashtable size of 4 and 10 entries. Now
the hashtable and element array look like that:

| 0     | 1         | 2 | 3 |
  |       |           |   |
  v       v           v   v
| a | b | c | d | e | f | g | h | i | j |

(with the array lengths etc set properly)

That way we don't have memory fragmentation, we don't need to really grow
arrays and the thing is fast and simple.

Ok, you convinced me ;)

>>You mean HashTableSize = NrOfEntries * LoadFactor ?
>>Certainly not less than 1, and more than 3 won't bring much more benefits.
>>I guess we'll simply have to experiment with that.
>>
>That depends on what you mean by "HashTableSize". Here, HashTableSize means
>"amount of positions in the table", and the formula is:
>
>LoadFactor = NrOfEntries / HashTableSize
>
>So, with a load-factor of 2, we have 2 times as many entries as we have
>positions, so, in average, each position has 2 entries.

Ah, ok. I thought it was the inverse of that. I'd rather use a value of 1
or even a bit lower. The extra memory is almost neglible and the (average)
speedup is really high (as the average chain length would be 1).

>>>Even if insertion doesn't take *alot* of time, I don't see why we wouldn't
>>>want to store it as we are going to be needing it. The code for
>PenguinFile

>The hash-function you propose doesn't take forever to run, but if you have
>5.000-10.000 entries, then I think you will find that it will take too long
>to hash each and every entry. Ok, pak files with 5.000-10.000 entries will

Cool, another misunderstanding ;)
Perhaps we could optimize our conversation by simply assuming beforehand
that we *will* misunderstand each other ;)

Of course storing the hash keys with the entries is good. What I meant was
that also storing "this entry is on position n in the chain" etc isn't good
(well, for arrays it might be ok - I was assuming lists back then, but it
again makes it neccessary that each entry knows exactly where in the hash
it is. This means more dependencies, uglier code and larger class
interfaces.)

>Using arrays and binary search, we still have O(log n) even in the
>worst-case.

Right.

>Actually, I considered using a hash-function quite similar to this. I
>decided not to because it does alot of multiplication, which is slow. Now
>that we've moved to a solely hash-table based solution, then the extra time
>used is worth it. However, using suchs a hash function, I do think we'll
>want to store hash-info.

Yup.

>>We'd of course have to do some benchmarking & tuning with it, but the
>>basics should be fine.
>>
>Outside of assembler-optimizations (which could take 4 to 8 bytes of the
>string in one iteration, based on the architeture), I don't see how you
>could make it faster.

I don't mean making it faster, but making it produce better (more evenly
distributed) hash keys for our situation (e.g. most filenames will have a
'.' character plus three alphabetic characters at the end, and these three
letter are often the same for all files in a given directory)

>>But again I agree. Preallocating space for n ppfFILE structs (1024 should
>>be fine. The only kind of software I know that really needs more are *very*
>>busy web servers. And we always can grow it if needed.)
>>
>I remember you saying that it would be perfectly ok behavior for a program
>to open all of the files it needs at start-up or level-load, and just keep
>them open. That could grow beyound 1024 in some games. But as you say, we
>can always grow.

Perhaps we can add some config option to change that value, but growing
that array shouldn't matter that much as well (after all it's just a matter
of allocating an additional array).

>My allocator has constant time performance for both allocation and
>deallocation. Allocation might cause the allocator to request more memory,
>but that is also constant-time.

Sounds very good.

>There are three drawbacks, however: Each allocator can only allocate memory
>in blocks of one size. This size is a constructor parameter, and cannot be

Usually ok. Is it possible to give it a hint about how many blocks will be
needed?

>changed at a later time, except for the condition in which the allocator is
>told to deallocate all of its memory. This means that my allocator will not
>be able to provide for strings, that is by definition variable-size.

The only place that I can see now where a custom allocator for strings
would be really useful is for the names of ppf_File and ppf_Directory
objects in format 0 Paks. The nice thing with these is that they are
essentially all freed at the same time, and it's either all or none. That
means no free space / fragmentation  management is required.
It should be relatively simple to write a proper allocator for this.

>The other drawback is that its very bad at returning memory to the heap.
>That is, doing that is a very expensive operation for it, and its O(n^2).
>I've designed it so that its possible to do this incrementally, so that it
>can be an idle-time job.

Doesn't matter usually

>The third drawback is that the allocator cannot allocate stuff that is less
>than 4 bytes.

No problem. You won't find any objects that are smaller than that on a
modern system.

>That string thing... I'll write an allocator that doesn't support
>deallocation, except for "everything at once", and that requires its exact
>size to be specified at construction. That could be used for strings, and
>would be very fast.

Keep the "exact size to be specified" out if possible. Making it growable
isn't too difficult (e.g. allocating memory in, say 4k blocks and on each
allocation checking ig the string completely fits in the remaining space of
the last block, allocating another one if not) and slow.


	Christian
--

Drive A: not responding...Formatting C: instead