Binary comparison of records?

[Robert Kosek]

I was thinking of creating a lookup system for a bunch of records, and because I don't want useless duplicate records I wanted to implement a lookup system. This way in my "constructor" the record is only made once, and all subsequent reference points to that one record.

But, how would I go about a binary comparison instead of a generic 'field = field' comparison? From what I know binary searches are easier and faster, and in a game this could be significant.

[Setharian]

not sure what you mean exactly.....if you want to return the same reference only when the data is EXACTLY the same (data passed to the contructor), then I'd say you could use some simple and fast hashing (CRC32 for example) - calculate the hash value for every created record and store it (inside the record itself or in a seperate array) and when you want to add a new record, calculate the hash for the new one and compare the hash with the already stored hashes...if a hash matches, you must perform a deep compare (field=field) because it may be possible 2 records can hash to the same value even when they have different data....to further reduce the the lookup time (you have to compare each hash), you could sort the array of records based on their hash value so you'd just do binary search to look for a hash value - if found, perform deep compare of records until you find the matching record or until you run out of hashes of the same value....if not found, you can be sure the record does not exist and you can add it to the list....

[Robert Kosek]

I mean instead of going (using a vector for example):
result := (a.x = b.x) and (a.y = b.y) and (a.z = b.z);

Is there a way to do a binary memory comparison? CRC checks are slower than the comparison above, but I was thinking along the lines of almost a binary "search" to see if the records are equal.

[Robert Kosek]

Nevermind, this function did it pretty well and pretty quickly too. :) That's pretty much a binary memory comparison unless I misunderstand it; Delphi SysUtils unit;
begin
result := CompareMem(@a,@b,SizeOf(Vector));
end;


Edit: And as you might expect, it's blazingly fast to boot ... however it seems no faster than the boolean comparison I posted previously.

[Setharian]

it is actually slower....the method I mentioned (checksums) or CompareMem are faster only with larger structures....

[Robert Kosek]

Really? Huh. I can see that with larger structures, but it can also really be a pain for those boolean checks the larger the record. ;)

Using gettickcount I found that both had a time of 0, I forgot the highlatency timer routines, so how did you test that out?

[JSoftware]

Using gettickcount I found that both had a time of 0, I forgot the highlatency timer routines, so how did you test that out?

for i := 0 to 1000000 do
:P

[Setharian]

I do not need to test it, the field=field compare - compares directly 3 32bit values so it's optimal for this situation, CompareMem is optimized for comparing large blocks so it has some overhead before actually comparing anything plus you have the function call overhead...

on win use QueryPerformanceCounter/Frequency to get times or RDTSC instruction....

[marcov]

Nevermind, this function did it pretty well and pretty quickly too. :) That's pretty much a binary memory comparison unless I misunderstand it; Delphi SysUtils unit;
begin
result := CompareMem(@a,@b,SizeOf(Vector));
end;


Be careful that this trick is only safe for PACKED records. If a record is not packed, you don't know what is in the alignment fields.



Edit: And as you might expect, it's blazingly fast to boot ... however it seems no faster than the boolean comparison I posted previously.

It requires a procedure call etc. If your vector is 16-bit you could cheat maybe like this:


type tvector = record
case boolean of
false : (x,y,z:integer); //assume tp 16-bit int!
true : (xandy:longint;z:integer);
end;

And then compare like
(a.xandy=b.xandy) and (a.z=b.z)

[Setharian]

for sure it's 32-bit float :)
about aligned records - unless allocated on the stack or directly by GetMem, you don't have to care...in these cases first clear it with zeroes using FillChar and you can safely use CompareMem with them (or easier solution with GetMem is to replace it with AllocMem)....

suffice to say, CompareMem would be fast if you'd be comparing 2 large records or arrays of records, otherwise it's slower...