Rockbox mail archive
Subject: RE: Search Plugin
From: TP Diffenbach (rockbox_at_diffenbach.org)
basically, the code I was looking at compiled (on 80x86 architectures) at
about 29Kb -- there's your plugin.
Given certain compromises (sub-optimal cache), a table could be opened for
about 7000 bytes, but we'd still need a place to store the strings returned.
Using Garsia-Wachs coding, we could expect efficiency somewhat less than
(non-adaptive) Huffman encoding, so I'd guess 60-80% of the original.
Assuming that track names are average 40 chars, encoded we'd get about 30.
30 * 100 = 3000b; call it 4096b, as we'd also need an array of pointers into
the buffer. The same space would hold 2048 shorts, assuming we used shorts
as ids; so 4096b would give us 1024 tuples in a cardinality reduction table.
For most table joins we'd have to process one or two cardinality reduction
So we might get away with as little as 12kb as a lower bound on working
memory, but I'd prefer twice as much. We can't really buy much by "wasting"
disk space: what we can buy is more entities in the cache by splitting the
tables a bit.
Minimum disk access is one for the starting table, one for each cardinality
reduction table, and one for each joined table. Since I'd have all joins go
through a track table, an Artist to Album join would require six reads:
Artist, artist-track cardinality-reduction, track-album crd, Album,
album-track crd, then track-data for the actually path. Clearly, if we have
enough memory to retain the track-album shorts when we read the Album data,
we could forego reading the album-track crd.
From: owner-rockbox_at_cool.haxx.se [mailto:owner-rockbox_at_cool.haxx.se]On
Behalf Of Björn Stenberg
Sent: Wednesday, December 17, 2003 6:41 PM
Subject: Re: Search Plugin
TP Diffenbach wrote:
> > -- database, database, database.
> Why do you think I asked about usage patterns in my poll? ;)
Excellent! See feature request #613544. :-)
> Another problem is working memory: unless we want to use the mpeg buffer,
> we'll need to limit the database to about 20KB of working memory; the code
> can /probably/ be loaded in the 32KB reserved for plugins, but the plugin
> API would have to be extended to allow the manipulation of playlists, and
> the database would probably need additional working memory.
My thinking about an ID3 database is that it should probably be a plugin,
simply because it's a GUI-grabbing function. At least my picture of it (a
tool for searching for tracks and building playlists).
I also think you should waste as much disk space as you want, if it saves
cpu processing and/or RAM needs. We all have gigs and gigs of disk space,
but just a few measly kilobytes of ram to play with.
I don't think you should worry about avoiding disk access, since that won't
be possible anyway. The database is on disk, and must be searched on disk.
Use the disk to its' fullest, that's what it's there for.
Page was last modified "Jan 10 2012" The Rockbox Crew