Re: Eaten by the Tiger? Open Source WO is coming...

On Aug 25, 2005, at 11:22 AM, Pierce T. Wetter III wrote:

> Which makes AJR much superior to EOF, as I commented, since EOF  
> uses NSArrays, and the last object is definitely not as fast as the  
> first object.
>
> I don't know where I got that AJR used NSArrays then, because I  
> remember reading the header file for an EOEditingContext.h and  
> seeing NSArray, and going "bummer" and moving on.
>
> So I apologize, and I'm much happier with AJR now. :-)
>
> Just out of curiousity, do you have any idea what the ratio of EOF  
> overhead to database fetch time is? We found that it was 3x, that  
> it took 3 times as long to fetch an object into EOF as it did to  
> fetch raw rows from Frontbase. Some of that was building the  
> objects (malloc, etc.) but a lot of it was registering the objects.

OK, here's a little about how EOF does work. In EOF, the editing  
context does in fact use NSMutableSet for it's backing store. Yes,  
the method -insertedObjects, -updatedObjects, and -deletedObjects  
return an NSArray, but the array is only constructed (and cached)  
when the above calls to those methods are made. So, EOF will not  
inherently slow down as more objects are fetched into the editing  
context.

However, both EOF and AJRDatabase make use of an optimization for  
objects that have integer (or long) primary keys. For EOF, they have  
a class called _EOIntegralPrimaryKey and AJRDatabase has a class  
called EONumericGlobalID. Yeah, they're different, but very low level  
and not used by the high level API's. The idea behind both these  
classes is that you can created a faster, more efficient global ID  
for objects that basically use an integer as their primary keys.  
Since in DB design, the vast majority of tables do use integers for  
their primary keys, this works out pretty well.

However, there's a problem with this. If you insert 100,000 (this was  
my test case) objects into a hash table (at least Apple's hash  
tables) where the hash function is basically linear, you'll find that  
performance serious begins to degrade. It appears that what happens  
is that very few buckets in the hash table are used, which basically  
results in a hash table with performance not all that much better  
than an array.

To compensate for this, AJRDatabase perturbs it's hash value in such  
a way that the values will never be linear. I had assumed that EOF  
would do the same, but from the slow downs other people have  
described, I'm going to assume that whatever perturbation they do  
isn't sufficient to produce non-linear or near non-linear results.

If anyone's really curious, AJRDatabase basically calls srandom 
(pkValue) followed by hash ^= random(). This produces very non-linear  
results over large data sets. For example, in my test case, with  
100,000 records, before I added the random function, I saw serious  
degradation of performance in the hash functions. So much so that is  
took multiple minutes for fetch the 100,000 records. After the  
change, AJRDatabase could fetch that many records in a fraction of  
the time. Basically, the last records fetched as fast as the initial  
records.

As a final note, this code will need to be updated a little bit once  
AJRDatabase supports full multithreading, since the key is relying on  
the behavior of random number generators to produce the same series  
of pseudo random numbers given the same initial seed. The problem, of  
course, is that if another thread calls random() between my call to  
srandom() and random(), we'll be one or more values down the sequence  
and thus won't produce the same hash key.

I hope this helps clarify what's going on under the hood in EOF and  
AJRDatabase.

Alex Raftis
---
[email protected]