Table Lookup Considered Harmful

Discussion in 'NZ Computing' started by Lawrence D'Oliveiro, Mar 24, 2010.

  1. In the source code for DVDAuthor (in subfont.c, if you want to follow
    along), in the “generate_tables†routine, there is this sequence:

    omtp = desc->tables.omt;
    for (i = 0; i < 256; i++)
    {
    for (mx = 0; mx < desc->tables.o_size; mx++)
    *omtp++ = (i * desc->tables.om[mx] + base / 2) / base;
    } /*for*/

    What this is doing is precomputing the results of multiplying every
    element of the “om†table by every one of the 256 possible 8-bit pixel
    values.

    The precomputed values are then used in the “outline†routine like this
    (“m†is the pointer to the “omt†table as computed above, “src†is the
    source pixel value):

    const register unsigned char * mp = m + msize * src + y1 * mwidth;
    int my;
    for (my = y1; my < y2; my++)
    {
    register int mx;
    for (mx = x1; mx < x2; mx++)
    {
    if (dstp[mx] < mp[mx])
    dstp[mx] = mp[mx];
    } /*for*/
    dstp += stride;
    mp += mwidth;
    } /*for*/

    This may have been a smart thing to do back in the 1980s, maybe even the
    1990s. But it isn’t any more. CPUs are so fast now that you might as
    well make use of them, don’t try to save instruction cycles by looking
    things up in memory instead. Do that, and you’re just asking to be
    bogged down by cache misses. Forget the lookup table, do the
    multiplication in the pixel-computation loop. It’ll be quicker.

    I gather this code originally came from MPlayer several years ago. I
    wonder what their version looks like now?
    Lawrence D'Oliveiro, Mar 24, 2010
    #1
    1. Advertising

  2. Lawrence D'Oliveiro

    Adam Guest

    Lawrence D'Oliveiro wrote:

    > In the source code for DVDAuthor (in subfont.c, if you want to follow
    > along), in the ?generate_tables? routine, there is this sequence:
    >
    > omtp = desc->tables.omt;
    > for (i = 0; i < 256; i++)
    > {
    > for (mx = 0; mx < desc->tables.o_size; mx++)
    > *omtp++ = (i * desc->tables.om[mx] + base / 2) / base;
    > } /*for*/
    >
    > What this is doing is precomputing the results of multiplying every
    > element of the ?om? table by every one of the 256 possible 8-bit pixel
    > values.
    >
    > The precomputed values are then used in the ?outline? routine like this
    > (?m? is the pointer to the ?omt? table as computed above, ?src? is the
    > source pixel value):
    >
    > const register unsigned char * mp = m + msize * src + y1
    > * mwidth; int my;
    > for (my = y1; my < y2; my++)
    > {
    > register int mx;
    > for (mx = x1; mx < x2; mx++)
    > {
    > if (dstp[mx] < mp[mx])
    > dstp[mx] = mp[mx];
    > } /*for*/
    > dstp += stride;
    > mp += mwidth;
    > } /*for*/
    >
    > This may have been a smart thing to do back in the 1980s, maybe even the
    > 1990s. But it isn?t any more. CPUs are so fast now that you might as
    > well make use of them, don?t try to save instruction cycles by looking
    > things up in memory instead. Do that, and you?re just asking to be
    > bogged down by cache misses. Forget the lookup table, do the
    > multiplication in the pixel-computation loop. It?ll be quicker.
    >
    > I gather this code originally came from MPlayer several years ago. I
    > wonder what their version looks like now?


    Take a look in spudec.c of MPlayer.
    Where similar looking stuff seems to be going on.
    Although I'm not sure where that example above exactly comes from.

    Through to the keeper for that one. Am busy tinkering with
    org-mode on Emacs again.
    Adam, Mar 24, 2010
    #2
    1. Advertising

  3. In message <hodv4t$qim$>, Adam wrote:

    > Am busy tinkering with org-mode on Emacs again.


    I have the following custom-set-variables entry in my Emacs prefs:

    '(auto-mode-alist (quote (("" . fundamental-mode))) t)
    Lawrence D'Oliveiro, Mar 24, 2010
    #3
  4. Lawrence D'Oliveiro

    Adam Guest

    Adam, Mar 25, 2010
    #4
  5. In message <hoebmm$217$>, Adam wrote:

    > For anyone on MS Windows wanting to use Emacs ...


    Hey, if they could handle Emacs, why would they be using Windows? :)
    Lawrence D'Oliveiro, Mar 25, 2010
    #5
  6. Lawrence D'Oliveiro

    Enkidu Guest

    Adam wrote:
    >
    > For anyone on MS Windows wanting to use Emacs, see below.
    >

    Oh great. The worst of both worlds. :cool:

    Come here for a decent editor:

    http://www.vim.org/download.php#pc

    Cheers,

    Cliff

    --

    The ends justifies the means - Niccolò di Bernardo dei Machiavelli.

    The end excuses any evil - Sophocles
    Enkidu, Mar 25, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joachim Krais
    Replies:
    2
    Views:
    15,034
    Andre Beck
    Nov 23, 2003
  2. John Ramsden
    Replies:
    0
    Views:
    888
    John Ramsden
    Jul 24, 2004
  3. zher
    Replies:
    2
    Views:
    8,975
  4. Lawrence D'Oliveiro

    Introductory Web Programming Considered Harmful

    Lawrence D'Oliveiro, Sep 16, 2005, in forum: NZ Computing
    Replies:
    20
    Views:
    998
    Mercury
    Sep 20, 2005
  5. Lawrence D'Oliveiro

    Spreadsheets Considered Harmful

    Lawrence D'Oliveiro, Mar 16, 2010, in forum: NZ Computing
    Replies:
    7
    Views:
    529
    Enkidu
    Mar 17, 2010
Loading...

Share This Page