pnathan: elephant bypasses fence to drink from pool (Default)
[personal profile] pnathan
An amusing anecdote from the Clink development trenches.

Intersection is, roughly, O(n^2). To be more precise, it's O(min(n,m)^2), where n and m are the lengths of the input vectors.

This turns out to be hugely important when implementing JOIN in a relational database, because you wind up intersecting n-ways for n tables.

Some empirical analysis of a 3-way intersection:

Intersect from largest to smallest:

CLINK> (time (ref *foo* :row 
   (multi-column-query *foo*
       `(1 ,#'(lambda (s) (find #\1 s))) 
       `(0 ,(lambda (x) (> x 300))) 
       `(3 ,(lambda (x) (> x 900)))))))
Evaluation took:
  4.015 seconds of real time
  4.149000 seconds of total run time (4.149000 user, 0.000000 system)
  103.34% CPU
  8,676,250,063 processor cycles
  1,252,768 bytes consed

And from smallest to largest:

CLINK> (time (ref *foo* :row 
   (multi-column-query *foo*
       `(1 ,#'(lambda (s) (find #\1 s))) 
       `(0 ,(lambda (x) (> x 300))) 
       `(3 ,(lambda (x) (> x 900)))))))

Evaluation took:
  0.766 seconds of real time
  0.879000 seconds of total run time (0.879000 user, 0.000000 system)
  114.75% CPU
  1,655,372,433 processor cycles
  1,074,592 bytes consed

We can clearly see that our runtime dropped by roughly 4x, cycles dropped about 7x, and our allocations by about 0.2x.

One of the most fun things about the Clink project is that it directly uses concepts from undergraduate computer science courses and applies them.
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
Account name:
If you don't have an account you can create one now.
HTML doesn't work in the subject.


Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Most Popular Tags

Expand Cut Tags

No cut tags
Page generated Sep. 25th, 2017 03:21 pm
Powered by Dreamwidth Studios