Re: [OctDev] optimized lookup

[Jaroslav Hajek]

On Feb 18, 2008 10:01 AM, David Bateman <address@hidden> wrote:
> Jaroslav Hajek wrote:
> > I've added an optimized compiled version of Octave's lookup into 
> > main/general
> > (main/general/src/lookup.cc). It seems to be faster in almost all
> > cases on my computer,
> > often much faster in the typical cases (downsampling, scarce lookup).
> > Any feedback is welcome.
> >
> >
> Jaroslav,
>
> Lookup is an octave core function and so it would be better if the
> decision was made to go with a compiled version of lookup to include it
> in Octave itself rather than in octave-forge.. Can you tell us what the
> improvements are.. Note that comments I've seen in the past about
> compiled code is that there should be some justification of why its
> better to use it rather than an m-file in terms of how often it is used
> and the size of the speed improvement, since the effort in maintaining
> C++ code is higher than m-files..
>
> D.
>
> --
> David Bateman                                address@hidden
> Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph)
> Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob)
> 91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax)
>
> The information contained in this communication has been classified as:
>
> [x] General Business Information
> [ ] Motorola Internal Use Only
> [ ] Motorola Confidential Proprietary
>
>

I agree. My intention was to put this into Octave-Forge for anyone interested,
so that anyone installing the Octave-Forge package gets the optimized
version (I think .oct files have "higher priority" than .m files).
If anyone of you Octave's maintainers decides that the function is worth
including into Octave itself, you can simply do it (and possibly remove
it from the Octave-Forge package).

Perhaps it would be a better idea to create a whole new package that
would contain
optimized (or otherwise improved) versions of Octave's library
functions, so that they can
be tested and eventually included.


Now for this optimized version itself, I'm reposting my previous email:

> hello,
> I have created an oct-file version of the "lookup" function currently
> found in scripts/general/lookup.m,
> that is used by several interpolation function.
>
> The original lookup.m uses a clever "hack" algorithm of concatenating
> the table and values
> together, performing sort, and extracting the appropriate indices. As
> noted in the original source,
> the complexity is O((M+N)*log(M+N)), where M is the size of the table
> and N the number of values,
> (disregarding the fact that Octave's sort performs better on partially
> sorted arrays).
>
> My new version traverses the values being looked-up sequentially in a
> single pass, and keeps
> locating the right interval by binary bracketing followed by a binary
> search. It is optimized for the
> common case of downsampling an existing table onto a sorted (or nearly
> sorted) denser grid.
> The asymptotic complexity is O(N*log(M)) as noted in lookup.m, which
> is thus faster for both
> M >> N and N >> M cases.
>
> I have also created a simple benchmark script to measure the speed-up effect.
> In the pessimistic case when the values are completely random, the new
> function is usually faster but
> sometimes also slower (I've seen at most 30%), depending probably on
> cache effects. In the almost
> sorted and sorted case, as well as in the case of large table and
> small amount of look-up values,
> the oct-file version is much faster.
>
> For example, on my Pentium-M 1.2GHz laptop, the m-version gives
>
> bechmark lookup
> table: 100000 sorted random numbers
> y: 4000000 random numbers
> y unsorted
> Elapsed time is 6.16387 seconds.
> y: nearly sorted (with fluctuations)
> Elapsed time is 2.78983 seconds.
> y: totally sorted
> Elapsed time is 2.26132 seconds.
>
> while the oct-version gives
>
> bechmark lookup
> table: 100000 sorted random numbers
> y: 4000000 random numbers
> y unsorted
> Elapsed time is 1.40393 seconds.
> y: nearly sorted (with fluctuations)
> Elapsed time is 0.133232 seconds.
> y: totally sorted
> Elapsed time is 0.0783129 seconds.
>
>

As you can see, I've made this optimization, because it is actually suggested
in the current m-file source for lookup. lookup itself is used by
several interpolation
functions; that's why I guess that the possibly increased maintenance cost may
pay off, but the decision is up to you.


regards,

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

lookup.cc
Description: Text Data

bench_lookup.m
Description: Text Data