wiredfool

Infrastructure

Been doing infrastructure programming recently. Basically trying to make sure that that light at the end of the tunnel is not a train. Since I’m not to the end of the tunnel yet, and it’s just something in software, I theoretically have the control to turn it into a ray of sunshine. But I digress.

I’ve been working on big table support for frontier. There’s a point in Frontier where big tables (> 10k items) become a performance bottleneck, and I’m trying to move that point out a couple of orders of magnitude, or at least far enough that other concerns dominate. I’m aiming for predictable performance for all tables, better performance for tables > 5k items, and reasonable performance for smaller ones. I also want it to be reasonably painless to integrate this with existing apps.

It’s actually not that hard to partition and nest tables in userspace, but it’s taking some rewriting of apps to really make it happen. And that’s the sticky part.

I hope to release the code soon, once the api stabilizes and I can call the core 1.0.

river ice on a tree branch, tulane road, va

PS to apple: dual 1ghz @ ~$2k would help with that oncoming train thing.

2 comments

2 Comments so far

  1. Commenter January 6th, 2002 4:56 pm

    Eric, what can you tell us about the api you’re working on?; Does it create a layer of table access behind which the actual table content is multiplexed?

    It’s actually not that hard to partition and nest tables in userspace, but it’s taking some rewriting of apps to really make it happen… I hope to release the code soon, once the api stabilizes and I can call the core 1.0.

  2. Commenter January 8th, 2002 8:10 pm

    Does it create a layer of table access behind which the actual table content is multiplexed?

    In short, yes. There are about 10 functions, newTable, sizeOf, defined, insert, delete, and address of: ithValue, specified key, item >= specified key, and next logical item. There’s also a stubbed out interface for commit and release of individual tables.

    I’ve got 4 table types implemented so far, a legacy flat, alpha sort, hashed (cases where alpha sort degenerates to 1 big table, such as when everything begins with http), and sequential (e.g. dg message table). I don’t really expect to use the flat one in production. The first one took half a day, the second 30 minutes. There are only 4 or 5 scripts different between them.

    Basically, once you have created the table and set a couple of optional attributes, all 4 types are exactly the same in the calling code. I’m also open to the very real possibility that I may be using this interface to store items outside the parent database, either in a seperate gdb or sql or the like.

    The biggest porting drawbacks are that I don’t have access to any gluecode for foo[i], foo.[key] or for adr in @foo. If those operators were implemented in kernel glue, then I could patch entirely at the kernel glue code level and not have to port.

    But as it is, I get constucts like the following, which actually isn’t that far off of what I’m using right now.

    adr = bigT.adrIthValue(adrTable, 1)
    while adr
    {stuff;
    adr = bigT.adrNextValue(adrTable, adr);}

    I’ve spent maybe a day and a half on the porting part, and I’ve been getting working code fairly quickly.

    As for the table details, all of the current table types are of the form as follows, where the fanout is between 1:16 and 1:100 at each level.

    foo
    meta
    container
    meta
    leafcontainer
    leaf
    leaf

    All leaves are on the bottom level, all containers know what containers they contain and how many elements are in each one. I suspect that access is effectively bounded by a constant time unless n gets really large, at which point it’s probably O(n^2/fanout^2). But at that point, either I can change table style again or I’ve run into a different Frontier limit.

Leave a reply

You must be logged in to post a comment.