On Tue, 16 Apr 2002 16:17:31 -0500, Rob Mayoff <[EMAIL PROTECTED]> wrote:
>+---------- On Apr 16, Jason Saunders said: >> Well, it seems the Ns_Cache functions weren't what I was looking for, but I >> have an idea of what might work... > >Have you prototyped any of this code to determine whether you even need >to worry about this? Premature optimization is the root of all evil. I originally had it all as a cgi with all data stored in a database, then each time the cgi ran it would do a query on the database for data on the X, then query again all the associated Ys ordered by about 5 columns, then put everything into a list, run the insertion algorithm to see if the new Y satisfied the right criteria, and then INSERT or UPDATE the database if it did. This took about .2 seconds if the query read data from disk, and about .02 seconds if the data was in cache. As the frequency of queries goes up, it all starts to slow down with reading from the database, ordering, building the structures, running the algorithm, updating the database, and freeing the structures. However, the process needs to be fast, so the idea is for the current data to be held on a dedicated machine which holds the Ys in order in memory. Then the process is just to see if the new Y satisfies the criteria, insert it in the correct place in memory and INSERT or UPDATE the database as a backup. My original plan was to use ColdStore to replace the database entirely and have all queries go directly to the mmapped data. However, it is good to have the abstraction of a database, so more general queries can be run, as well as mirroring it for failover/backup. Then the database can be used for less time-critical operations such as listing past and current data for a user etc. With the database there, there's no need for using ColdStore and mmap to store the data, but the idea of having related data stored in the same extent is appealing for the reason you mention i.e. maximising processor cache hits during sequential access. Your idea of storing the bids in an array works. Even if the array gets full, a new larger array can be allocated and the data copied. As an optimisation, the array tail could be shifted while waiting for confirmation of INSERT or UPDATE from the database. (Any idea how to go about this?) My concern is that the number of Ys per X is variable, so using an array would consume more memory than necessary, and if the array is filled, then the whole array must be copied to a new larger one. Also, is there a significant difference between sequential and random reads within an Intel processor cache? Since if the difference is minor, I think lists would win as inserts are so much quicker and simpler. Cheers, Jason >> To ensure locality of the linked lists (of type Y objects), I can allocate a >> stack of 4k or 8k and a stack access mutex as each type X object is created, >> to be used to store the type Y objects associated with the new type X >> object. And then by keeping a pointer to the top of the stack I can then add >> type Y objects to the stack and keep them local to each other. >> >> Then the type X objects could be put in hashes. >> >> How does that sound? > >If you're only talking 8K bytes of objects, then I question whether you >really have enough objects to worry about locality of reference. How >many Xs are you talking about? > >Furthermore, given such a small number of Ys, you might be better off >storing the Ys in an array, and simply shifting the tail of the array >when you need to insert an element. This will maximize your cache hits >during sequential access (which is probably what you really mean when >you talk about locality). Whether this is a better approach depends on >the ratio of insertions to accesses. > >None of this is worth doing until you have a prototype on which you can >actually measure the performance.
