|♩♬♫♩♪ |

i read Knuth chapter 6.1-6.5 when i wanted to start at the utmost basic in searching/sorting implementation.. the current academic papers are way too specialized, and the main open-source DB engines are more interested in explaining how to write a SQL statement, or how much money youll save switching off Oracle, than talk about anything interesting.

i've some primal instinct of whether something is O(1) or O(n^2) but never really considered how much is influenced by how the code is written, regardless of the underlying (overarching?) algorithm affecting the order-of-magnitude scaling. i just figured 'perl/ruby is slow no matter what' and any way is good as another, with 300 ways of doing anything how are you supposed to try them all anyway?

since i never had a formal education, i definitely had some confidence issues. like was i missing some big chunk of CS? it was comforting to realize there was nothing in the book that seemed completely foreign (alright, except the proofs..) and his optimization strategy boils down to reading code, thinking about it, and making improvements. it gave me confidence to see his methods are plain sucking it up and using your brain for a minute, something within my reach.

back to the Planet example..

the first implementation of the fetch just tries adding every triple, whether it existed or not. this generates a filestat per triple, along with URI and object-construction in Ruby, and fetched-data destruction. every time the update runs, the disk light glows bright blue for about 10 solid seconds. then its done.

time is your friend...

user    0m2.920s
sys     0m1.098s

user    0m2.920s
sys     0m1.098s

the kernel is spending a full on second just doing file stats for the hundreds of blog posts and their thousands of triples.

the disk grind this creates gives me that same 'ugh' feeling as when firefox takes 30 seconds to boot up.. i know its unacceptable, but so far ive been too lazy/busy to get around to fixing it. no longer! (replacing firefox is a larger project, to be detailed in later posts)

my thought was 'check each resource to see if its already there, then write it if need be'. constructing a temporary model for querying of Date attributes and for writing into the real model as necessary:

  def update
    n=get
    n.keys.map do |u|
      e=E(u)
      e.e || e.in_hash(n[u])
    end
  end

  def get
    r={}
    _in do |s,p,o|
      r[s] ||= {}
      r[s][p] ||= []
      r[s][p].push o
    end
    r
  end

  def in_hash h
    h.map do |p,vs|
      vs.each{|v| self[p,v]}
    end
  end

well, the disk grind is gone, but it doesnt seem much faster. hmm. maybe all that object creation/allocation is expensive.

user    0m1.944s
sys     0m0.400s

user    0m1.947s
sys     0m0.360s

user    0m1.982s
sys     0m0.363s

the sys is doing less than before, as expected. ruby is mainly setting references rather than constructing objects, for a sizable reduction in work. i really love how consistent 'time' is, and the C ruby VM. JRuby was all over the place, and you had to run 10 times before it sort of stabilized. 'enterprise-grade' unpredictability..

my instinct (primed by the stuff Knuth pulls out in his MIX optimizations) tells me theres more to be squeezed out of this. i can run the check each time i see a new resource.and keep a running tab of the checked resources, while consuming the original stream of triples from the parser.

  def update
    e={}
    _in do |s,p,o|
      r=E(s)
      (e[s] ||= r.e) || r[p,o]
    end
  end

this is the kind small improvement that while not the difference between n and n^2 but well worth the brief amount of time that is code-review.

user    0m1.374s
sys     0m0.132s

user    0m1.398s
sys     0m0.142s

indeed, ruby is doing even less work than before. presumably the 1 second or so left is mainly Redland's parsing and object creation, which I can't really avoid. lets check to see if the blame is really out of my territory:

 %self     total     self     wait    child    calls  name
  9.88      0.75     0.32     0.00     0.43    19595  Class#new
  9.26      3.24     0.30     0.00     2.94        6  Array#map
  9.26      0.30     0.30     0.00     0.00        9  <Module::Redland>#librdf_parser_parse_as_stream
  2.78      0.09     0.09     0.00     0.00     4572  <Module::Redland>#librdf_new_node_from_node
  2.47      0.08     0.08     0.00     0.00    13729  Kernel#class
  2.16      0.07     0.07     0.00     0.00    13263  <Module::ObjectSpace>#define_finalizer
  2.16      0.07     0.07     0.00     0.00     3690  <Module::Redland>#librdf_statement_get_object
  2.16      0.07     0.07     0.00     0.00     3891  <Module::Redland>#librdf_node_get_uri
  1.54      0.05     0.05     0.00     0.00     2688  <Module::Redland>#librdf_new_node_from_literal

re: Array#map, I got a 6x (!) slowdown after factoring some of the subexpressions in Hydrogen into seperate functions. i had no idea ruby had that kind of function call penalty, none of my functions are longer than a single expression and a guard pattern; if more performance was needed here the next step is switch to something with a real compiler and type system and without pointless distinctions between 'blocks', 'procs', and 'methods' needlessly complicating things from implemenetations to code to books.

theres one more boost, cpu was on 0.8 instead of 2g.

echo performance > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor

user    0m0.673s
sys     0m0.058s


user    0m0.679s
sys     0m0.057s

and voila. the kernel has plent of time to waste on epolling torrent downloads again. its too bad theres nothing to leech. i am thinking of just taking rlslog out of the default list and isohunting Twitch posts.. or making my own flicks

the prior half of 'planet in 2 lines':

 E(E::Type,'planet/source').po(E(E::RSS+'channel')).map{|b| b.gr('planet/posts').in}

defined the input pipe. adding some new sources:

%w{http://engadget.com/rss.xml
   http://newsrss.bbc.co.uk/rss/non/front_page/rss.xml
   http://feeds.boingboing.net/boingboing/iBag}.each{|u|
   E(u,'planet/source')[E::Type,E::RSS+'channel']}

gives a good mishmash of random news..

we need a view on the data. how about plain old HTML..

finding the proper resources is a matter of a depth-first search on the date URIs - literals are expressible as URIs which simplifies literal sorting infrastructure down to a single search in the AVL-ish tree of URIs on the fs. incidentally Kowari/Mulgara uses the same technique but i decided Hans Reiser could write a better tree and expose it via a classic 40 year-strong API than i could. although i'll definitely experiment with the AVL module in the Haskell port, especially for in-memory indexing. if someone hires me or pays me anyway.. slow ass Ruby and its C calls are more than fine for my needs..

html do
  style <<-S
    body {background-color: #444}
    .p {float:left;height:8.8em;position:relative;overflow:hidden;width:20%;-moz-border-radius:0 1em 1em 1em;background-color:#264;color:#fff}
    .t {background-color:#00f;color:white;display:inline}
    img {max-width:100%}
  S
  body do
    h1 "today's headlines"
    E(Date,'planet/posts').iT(64).each do |r|
      div.p :onmouseover => 'this.style.overflow="scroll"' do
        h3.t r.i(RSS+'title')
        %w{modules/content/encoded description}.each{|c| self << r.i(RSS+c)}
     end
    end
  end
end

whats going there? first its Markaby - HTML as Ruby. we're lazily grabbing the fields we decided we wanted, and throwing them into a layout. after a request, its cached:

####
T 127.0.0.1:46418 -> 127.0.0.1:80 [AP]
  GET /planet HTTP/1.1..Host: m..User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:
  1.8.1.11) Gecko/20071221 BonEcho/2.0.0.11..Accept: text/xml,application/xml,application/
  xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5..Accept-Language: en-us,e
  n;q=0.5..Accept-Encoding: gzip,deflate..Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7..
  Keep-Alive: 5..Connection: keep-alive..If-Modified-Since: Tue, 22 Jan 2008 15:56:36 GMT.
  .If-None-Match: "47961234-6fd3-1ec6cd8"..Cache-Control: max-age=0....                   
##
T 127.0.0.1:80 -> 127.0.0.1:46418 [AFP]
  HTTP/1.1 304 Not Modified..Connection: close..Date: Tue, 22 Jan 2008 16:19:08 GMT..Conte
  nt-Encoding: gzip..ETag: "47961234-6fd3-1ec6cd8"....                                    

theres more that can be done. breaking out the resource preview into its own layout. generalizing the view data-source so that tabulator or other RDF tools can see the same thing we're showing in HTML, etc. this took only a minute to whip up, and the granularity and modularity of the components are awaiting bespoke adjustment to the situation..