SV: Progress Update

["Bjarke Hammersholt Roune" <asmild@post6.tele.dk>]

>>Well, yes, but then qsort() is not the only thing happening. The indexing
>>needs to examine the hash value of each entry in the entry array. This is,
>>of course, O(n), and thus, the whole thing is, combined O(n).
>
>No ;)
>
>O(n log(n)) > O(n)
>
>So the whole thing is, combined O(n log(n))
>

<Bjarke looks for that gun he has somewhere, to shoot himself>
<Luckily, he couldn't find it>
(or unluckily, depends a little on one's perspective)

Of course. What I understod you to say was O(log n). Of course, you didn't
say O(log n), but O(n log n). You are completely correct.

>>Nice. I'll have a look at DocBook. I think I'll write a little something
>>about how to decide wheter or not to sue an allocator, and, if one is
used,
>                                      ^^^
>I didn't know they are *that* evil ;)
>
Vermin from hell, I tell you! Protect youself while you can! They'll happily
eat your family and steal your house!

I'm very proud of them ;)

>>This is extremely slightly ineffecient. If the URL string pointer and the
>>length could be stored in a member-struct/class of the URL class. That
way,
>>a reference can be used as KEY instead, and then only 4 byte is copied,
>>instead of 8, as is the case in the implementation mentioned above.
>
>Well, you can also pass a ppf_URLInfo& and an integer, so that the hash can
>access the string via UInfo.GetPartStart (int) and its length via
>UInfo.GetPartSize (int)
>
That would be ineffecient, as both GetPartStart() and GetPartSize() makes a
look-up, which is unnessecary.

>I guess it doesn't matter what is done where - the size of the data to be
>passed and the required processing always stay about the same.
>
I just realised that this matter anyway because of inlining. As an example,
this is what happens every time a searched-for-key is matched against an
entry:

MISC::Compare(key, MISC::GetKeyOf(entry));

Now, the invocations of MISC::Compare() and MISC::GetKeyOf() both get
inlined, and result in this:

strncmp(key.m_pName, entry.GetName(), std::min(key.m_nameLen,
entry.GetNameLen());

And keys aren't copied anywhere. Well, ok, ONCE we need to, to change to the
correct format for the key when passing a key as the parameter of the
GetEntry() method.

That leads me to another thing, which is that to get evaluate wheter one
file name is lesser than, equal to or greater than another file name, we
need to add a GetNameLen() function to DirEntry (ppf_DirEntry).

The reason we need this is to make the binary search utilised by HashTable
when searching array segments work. We could also just do a serial search of
an array segment that needs to be searched, but that would change worst case
performance from O(log n) to O(n). With the serial search, we just need to
know wheter two strings match, and, as the case is, we know the length of
one string, and the other is null-terminated, we don't need to get the
length of the name of directory entries.

>NO! Then we'd have a situation where game A, which is written for a
>dos-style-path using PFile has to be installed on a system with a
>unix-style-path using PFile. Chaos.
>
I was thinking of static linking for this, though.

>>>because bool values are internally just perfectly normal ints
>>>
>>Actually, its only 1 byte.
>
><checking> Right. Strange - byte processing is AFAIK sometimes slower than
>int
>
If you have 2,3 or anything else that is not divisable by 4 (or 8, depending
on the platform), you'll get a sligth performance loss, since the computer
will then do  each byte one at a time.

This doesn't matter if you have just 1 byte, since you'll be doing it "one
at a time" anyway. Nothings preventing you from padding your classes, so I
think its a very good idea to have bool be 1 byte.