httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stefan Fritsch>
Subject Re: Optimising ap_location_walk()
Date Sun, 24 Oct 2010 13:50:01 GMT
On Sun, 24 Oct 2010, Graham Leggett wrote:
> I'm not keen to change the semantics at all, I'd rather like to speed up the 
> array lookup from the linear search we do now.
> I went on a hunt for efficient string prefix matching algorithms, but that's 
> led me into some heavy computer science theory where the bulk of the work was 
> on prefix matching IP addresses rather than strings (which seems to be a 
> problem that's received more attention).
> I think the hashtable approach would be reasonable, given that we have the 
> option to pre-create the index at startup post_config.

I am probably missing the obvious, but how do you intend to do the hash 
lookup? Given that <Location /app> also matches the dir /application, you 
may have to do N lookups for an url of length N.

Have you considered using a trie or a binary search tree?

View raw message