apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Pane <brian.p...@cnet.com>
Subject Re: Frankentables
Date Sun, 11 May 2003 03:13:06 GMT
I've been meaning to review this patch for the past week,
but I haven't had time to give it the attention it deserves.
For now, some general thoughts on the design...

On Sat, 2003-05-10 at 15:22, Joe Schaefer wrote:
> Joe Schaefer <joe+gmane@sunstarsys.com> writes:
> 
> [...]
> 
> > Has anyone given any thought to the changes I proposed
> > to the table implementation?
> 
> Hmm, since the patch to apr_tables.c is pretty large, 
> maybe I should start by posting the small patch to 
> apr_tables.h and discuss that first.
> 
> Here is a list of the changes:
> 
>   1) use a native unsigned int for the key_checksum.  This should
>      allow 64 bit machines to use 8 chars for the table hash & key_offset
>      instead of just 4.

Back when I put the current checksum support into apr_table,
I found that making the checksum *too* good was detrimental
to performance, at least when using httpd-2.0 as a test case.
The problem was that apr_table_addn() is called a lot.  Before
checksums, that function only had to do one if-statement and
a little bit of pointer arithmetic in the common case.  The
cost of computing the 4-byte checksum was nontrivial in
comparison. So apr_table_addn() got slower, but the total time
spent in table operations was reduced.  With an 8-byte checksum,
you might find that the extra time spent computing checksums
makes the table code slower overall for apps that do a lot
of adds.  (This should be easy to test, though.)

>   2) superimpose a tree-node onto the table entry, with a next
>      node to keep track of multivalued keys.  These are implemented
>      as ints (which represent offsets from t->a.elts) instead of 
>      raw pointers to memory addresses.  This is necessary to allow
>      the underlying array to realloc itself as new entries are added.

+1 on using offsets instead of pointers.  That makes it easier to
debug, too.

>   3) add some bitfields to the table_entry:
> 
>         key_offset- marks where the checksum leaves off so we 
>                     don't have to start strcasecmp at the start of
>                     the string.
>         color- tracks the color (red or black) of the entry.

I have a feeling the addition of the red-black trees will help
performance a lot for large tables but may hurt for small tables.

>         dead-  marks the entry as dead.  Dead entries are entries
>                that were removed from the table, but haven't been
>                "paved over" yet by shifting & reindexing the remaining
>                (live) entries.  Potential dead entries are expunged
>                from the table by calling apr_table_elts().

The only thing that worries me here is that apr_table_elts()
currently is declared as a const "method."  Right now, it's
legitimate for a module to create a table during startup and
then do something like this during request processing:

  const apr_array_header_t *arr = apr_table_elts(conf->some_table);
  const apr_table_entry_t *elts = arr->elts;
  /* iterate through elts... */

If there are any dead entries in the table after initialization,
the first request to hit that code will compact the table during
the apr_table_elts() call.  But if multiple threads happen to hit
that bit of code concurrently, some of them will end up getting
a corrupted view of the table.  (I used an httpd example here,
but any threaded app that currently relies on the constness of
apr_table_elts() will have problems if it becomes non-const.)

For the httpd, we'll have to maintain binary compatibility until
2.1.  That doesn't necessarily mean that the table code in APR
can't change sooner, just that we won't be able to take advantage
of it in httpd-2.0.

If you have a chance to do any performance testing and/or profiling,
I'd be really interested in seeing the results.  If the new table
code is faster than the current code for small tables (as are
common in the httpd), then IMHO it would be worthwhile to try to
make apr_table_elts() const in the new code.  (Hmmm...would it
be possible to do table compaction in O(1) time inside
apr_table_unset() by just swapping the deleted element with
the one at the end of the array and updating the swapped node's
parent's and children's pointers to reflect its new location?)

Alternately, if the new code performs better for large tables
(which is almost a certainty, given the design) but worse for
small tables, another option would be to support both APIs--call
the new one apr_bigtable_t or something like that.

Brian



Mime
View raw message