Uploaded image for project: 'WiredTiger'
  1. WiredTiger
  2. WT-839

Application-specified collators & error handling in btree search loop

    XMLWordPrintable

    Details

    • Type: Task
    • Status: Closed
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: WT2.1
    • Component/s: None

      Description

      The Berkeley DB change to the application-specified comparison function API may be interesting. The change was to add a reference to a size_t as an additional 4th argument to the comparison function, but oddly enough, the applications aren't supposed to touch that new argument.

      What's happening is BDB has the same code we have to skip over common prefixes when doing a binary search through page keys, which requires the comparison function return the longest matching prefix on each comparison, and that's the reason for the additional argument. Rather than add a test/branch into the btree search inner loop, BDB changed the application-specified comparison function signature to take the additional argument just like the internal comparison function.

      We're doing it with a test:

      #define WT_LEX_CMP_SKIP(s, collator, k1, k2, cmp, matchp)
              ((collator) == NULL ?
              (((cmp) = __wt_lex_compare_skip((k1), (k2), matchp)), 0) :
              (collator)->compare(collator, &(s)->iface, (k1), (k2), &(cmp)))
      

      Further, the only reason for error handling on this call is because application-specified collators can fail, our collator cannot fail.

      I replaced the search loop calls to WT_ERR(WT_LEX_CMP_SKIP()) with a call to __wt_lex_compare_skip(), removing the error handling, and it improves my test by over 6% with gcc 4.7 on my FreeBSD 9.1 box. In an in-cache, 5M row table, search for every row in order, I go from .5788 usecs per search to .5416 usecs per search.

      I don't see a simple way to make this change for real, but 6% seems like it's worth having on searches.

      Thoughts?

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                keith.bostic Keith Bostic
                Reporter:
                keith.bostic Keith Bostic
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: