Cliff: Kind of funny. While reading all these helpful e-mails, I was telling myself "so really, what I need to do is build some sort of state machine..." and there the phrase was in your latest e-mail.
OK, so with everybody's help, I think I have everything I need (most especially the outline for an improved algorithm) to deliver improved accuracy *and* performance finding the cookie in mod_usertrack. I guess it's time to get hacking. -Manni -------------------------------------------- Manni Wood, Programmer, Digitas 800 Boylston Street, Boston, MA, 02199 617 867 1881 [EMAIL PROTECTED] "Most men would rather die than think. Many do." --Bertrand Russell -----Original Message----- From: Cliff Woolley [mailto:[EMAIL PROTECTED] Sent: Tuesday, February 25, 2003 5:44 PM To: [EMAIL PROTECTED] Subject: RE: mod_usertrack bugfix patch On Tue, 25 Feb 2003, Manni Wood wrote: > Interesting you should mention this. An older version of the patch I > wrote (I've been working on the problem off an on for over a year) did > what you said: loop over the delimiters and parse each name=value pair > into an apache table. Then, I asked the apache table if the cookie was > present. (These older patches are linked to from > http://manniwood.net/mod_usertrack_patch.html, at the bottom of the > page.) Yes, I saw that on your page. (Good work on that, by the way. I agree with Jeff that it's a great resource.) But even the expense of creating a table is unneeded. If you put all the values into a table and look the one you want up afterward and then throw the whole table away, that's a lot of unneeded expense. Building a table means building a red/black tree and all kinds of goo that we don't need for a simple matching process. This runs in something like O(nlogn) time with a high constant coefficient where n==strlen() (I'd have to go reread apr_tables.c to be sure about the exact time complexity). If the current cookie isn't the one you want, strcmp() will tell you that. As soon as you find the one you want, you're done. Move on to the next one and try it. And actually, you can do even better than strcmp()... just use a loop that does the comparisons a character at a time so you don't have to ever examine any character more than once. It's a simple little state machine. In essence, comparing against the regex is doing the same thing, but since it's simple the readability won't be bad, and you can get better performance out of it than calling into a regex engine would give you. This method will in straight-up O(n) time. --Cliff
