Empathy List Archives

RD

Revar Desmera

Wed, Oct 4, 2023 9:53 PM

Two very easy, backwards-compatible changes to the lookup() builtin that would be very helpful:

It would be nice if the lookup table that lookup() searches into, could have vectors as payload values. ie:

table = [
[0, [-50,0,0]],
[0.3, [-20,-10,25]],
[0.7, [ 20,10,25]],
[1, [ 50,0,0]],
];
for (u = [0:1/32:1])
move(lookup(u, table))
sphere(d=1);

This can (and has) been done in user-space using `search()`, but at a severe cost of efficiency.

If the search value given is a range type, return a list of results, one for each value of the range:

table = [
[0, [-50,0,0]],
[0.3, [-20,-10,25]],
[0.7, [ 20,10,25]],
[1, [ 50,0,0]],
];
for (pt = lookup([0:1/32:1], table))
move(pt)
sphere(d=1);

This also can be done in user-space using a simple list comprehension, but there are obvious optimizations by doing it built-in, that take the efficiency from O(n^2) in user-space to O(n) in C++.  There are actually quite a few places in my library that could take great advantage of that.

For example, enveloping worm creation could be made a lot faster. I suspect bezier surfaces could be optimized a lot, albeit with a minor loss of accuracy.

These changes should be fairly trivial to implement. I'd do it myself, but my submissions have had a 0% acceptance rate into the mainline code, so far.

-Revar

Two very easy, backwards-compatible changes to the `lookup()` builtin that would be very helpful: 1. It would be nice if the lookup table that `lookup()` searches into, could have vectors as payload values. ie: table = [ [0, [-50,0,0]], [0.3, [-20,-10,25]], [0.7, [ 20,10,25]], [1, [ 50,0,0]], ]; for (u = [0:1/32:1]) move(lookup(u, table)) sphere(d=1); This can (and has) been done in user-space using `search()`, but at a severe cost of efficiency. 2. If the search value given is a range type, return a list of results, one for each value of the range: table = [ [0, [-50,0,0]], [0.3, [-20,-10,25]], [0.7, [ 20,10,25]], [1, [ 50,0,0]], ]; for (pt = lookup([0:1/32:1], table)) move(pt) sphere(d=1); This also can be done in user-space using a simple list comprehension, but there are obvious optimizations by doing it built-in, that take the efficiency from O(n^2) in user-space to O(n) in C++. There are actually quite a few places in my library that could take great advantage of that. For example, enveloping worm creation could be made a lot faster. I suspect bezier surfaces could be optimized a lot, albeit with a minor loss of accuracy. These changes should be fairly trivial to implement. I'd do it myself, but my submissions have had a 0% acceptance rate into the mainline code, so far. -Revar

JB

Jordan Brown

Thu, Oct 5, 2023 12:08 AM

On 10/4/2023 2:53 PM, Revar Desmera wrote:

It would be nice if the lookup table that lookup() searches into,
could have vectors as payload values. ie:

PR#4274 is exactly that. I'm not sure why it stalled - probably because
reviewers (notably including me) asked for a fair number of minor checks
and test cases. I don't think any of them are hard, but they are
tedious and take time and effort, and like all of us the submitter
probably has serious limits on both.

On 10/4/2023 2:53 PM, Revar Desmera wrote: > 1. It would be nice if the lookup table that `lookup()` searches into, > could have vectors as payload values. ie: PR#4274 is exactly that. I'm not sure why it stalled - probably because reviewers (notably including me) asked for a fair number of minor checks and test cases. I don't think any of them are hard, but they are tedious and take time and effort, and like all of us the submitter probably has serious limits on both.

JB

Jordan Brown

Thu, Oct 5, 2023 12:16 AM

On 10/4/2023 2:53 PM, Revar Desmera wrote:

If the search value given is a range type, return a list of
results, one for each value of the range:

table = [
[0, [-50,0,0]],
[0.3, [-20,-10,25]],
[0.7, [ 20,10,25]],
[1, [ 50,0,0]],
];
for (pt = lookup([0:1/32:1], table))
move(pt)
sphere(d=1);

Is this semantically the same as

for (i = [0:1/32:1]) {
pt = lookup(i, table);
move(pt)
sphere(d=1);
}

Is the gain only that the second iteration can search less of the table?

I think lookup is a binary search, O(log(n)), so this is already
O(n*log(m)); eliminating half of the entries is only a 1/log(m)
improvement, and k is pretty small.

On 10/4/2023 2:53 PM, Revar Desmera wrote: > 2. If the search value given is a range type, return a list of > results, one for each value of the range: > > table = [ > [0, [-50,0,0]], > [0.3, [-20,-10,25]], > [0.7, [ 20,10,25]], > [1, [ 50,0,0]], > ]; > for (pt = lookup([0:1/32:1], table)) > move(pt) > sphere(d=1); > > Is this semantically the same as for (i = [0:1/32:1]) { pt = lookup(i, table); move(pt) sphere(d=1); } Is the gain only that the second iteration can search less of the table? I think lookup is a binary search, O(log(n)), so this is already O(n*log(m)); eliminating half of the entries is only a 1/log(m) improvement, and k is pretty small.

RD

Revar Desmera

Thu, Oct 5, 2023 1:05 AM

On Oct 4, 2023, at 5:16 PM, Jordan Brown openscad@jordan.maileater.net wrote:

Is the gain only that the second iteration can search less of the table?
I think lookup is a binary search, O(log(n)), so this is already O(n*log(m)); eliminating half of the entries is only a 1/log(m) improvement, and k is pretty small.

Looking at the code, it is definitely NOT doing a binary search. It's doing a linear search to find the largest key that is <= the searched for key, and the smallest key that is >= the searched for key, then interpolates using those two keys and their associated values.

Revar

> On Oct 4, 2023, at 5:16 PM, Jordan Brown <openscad@jordan.maileater.net> wrote: > > Is the gain only that the second iteration can search less of the table? > I think lookup is a binary search, O(log(n)), so this is already O(n*log(m)); eliminating half of the entries is only a 1/log(m) improvement, and k is pretty small. > Looking at the code, it is definitely NOT doing a binary search. It's doing a linear search to find the largest key that is <= the searched for key, and the smallest key that is >= the searched for key, then interpolates using those two keys and their associated values. - Revar

JB

Jordan Brown

Thu, Oct 5, 2023 1:15 AM

On 10/4/2023 6:05 PM, Revar Desmera wrote:

On Oct 4, 2023, at 5:16 PM, Jordan Brown
openscad@jordan.maileater.net wrote:

I think lookup is a binary search, O(log(n)), so this is already
O(n*log(m)); eliminating half of the entries is only a 1/log(m)
improvement, and k is pretty small.

Looking at the code, it is definitely NOT doing a binary search. It's
doing a linear search to find the largest key that is <= the searched
for key, and the smallest key that is >= the searched for key, then
interpolates using those two keys and their associated values.

OMG that's terrifying. I don't know why anybody would define it that way.

But then I'm not sure how your range construct would help, because for
each step in the range the matching two entries might be anywhere in the
table. (For a large enough number of steps it might be better off
internally sorting the table and then using a binary search, but yuck.)

On 10/4/2023 6:05 PM, Revar Desmera wrote: >> On Oct 4, 2023, at 5:16 PM, Jordan Brown >> <openscad@jordan.maileater.net> wrote: >> >> I think lookup is a binary search, O(log(n)), so this is already >> O(n*log(m)); eliminating half of the entries is only a 1/log(m) >> improvement, and k is pretty small. >> > Looking at the code, it is definitely NOT doing a binary search. It's > doing a linear search to find the largest key that is <= the searched > for key, and the smallest key that is >= the searched for key, then > interpolates using those two keys and their associated values. OMG that's terrifying. I don't know why anybody would define it that way. But then I'm not sure how your range construct would help, because for each step in the range the matching two entries might be anywhere in the table. (For a large enough number of steps it might be better off internally sorting the table and then using a binary search, but yuck.)

RD

Revar Desmera

Thu, Oct 5, 2023 1:18 AM

On Oct 4, 2023, at 6:15 PM, Jordan Brown openscad@jordan.maileater.net wrote:

On 10/4/2023 6:05 PM, Revar Desmera wrote:

On Oct 4, 2023, at 5:16 PM, Jordan Brown openscad@jordan.maileater.net mailto:openscad@jordan.maileater.net wrote:
I think lookup is a binary search, O(log(n)), so this is already O(n*log(m)); eliminating half of the entries is only a 1/log(m) improvement, and k is pretty small.

Looking at the code, it is definitely NOT doing a binary search. It's doing a linear search to find the largest key that is <= the searched for key, and the smallest key that is >= the searched for key, then interpolates using those two keys and their associated values.

OMG that's terrifying. I don't know why anybody would define it that way.

But then I'm not sure how your range construct would help, because for each step in the range the matching two entries might be anywhere in the table. (For a large enough number of steps it might be better off internally sorting the table and then using a binary search, but yuck.)

Well, apparently it allows for out-of-order entries in the lookup table, without incurring the expense of a sort. But yes, this precludes the optimization I was hoping for, unless range searches just required that the table keys increased monotonically.

Revar

> On Oct 4, 2023, at 6:15 PM, Jordan Brown <openscad@jordan.maileater.net> wrote: > > On 10/4/2023 6:05 PM, Revar Desmera wrote: >>> On Oct 4, 2023, at 5:16 PM, Jordan Brown <openscad@jordan.maileater.net> <mailto:openscad@jordan.maileater.net> wrote: >>> I think lookup is a binary search, O(log(n)), so this is already O(n*log(m)); eliminating half of the entries is only a 1/log(m) improvement, and k is pretty small. >>> >> Looking at the code, it is definitely NOT doing a binary search. It's doing a linear search to find the largest key that is <= the searched for key, and the smallest key that is >= the searched for key, then interpolates using those two keys and their associated values. > > OMG that's terrifying. I don't know why anybody would define it that way. > > But then I'm not sure how your range construct would help, because for each step in the range the matching two entries might be anywhere in the table. (For a large enough number of steps it might be better off internally sorting the table and then using a binary search, but yuck.) > Well, apparently it allows for out-of-order entries in the lookup table, without incurring the expense of a sort. But yes, this precludes the optimization I was hoping for, unless range searches just required that the table keys increased monotonically. - Revar

OA

oz.at.michael@gmail.com

Thu, Oct 5, 2023 1:21 AM

Note that interpolation was always the intent of lookup(), judging by the original examples. Search() is for searching.

JB

Jordan Brown

Thu, Oct 5, 2023 1:24 AM

On 10/4/2023 6:21 PM, oz.at.michael@gmail.com wrote:

Note that interpolation was always the intent of lookup(), judging by
the original examples. Search() is for searching.

It's not the interpolation that we're being surprised by. It's the fact
that the entries aren't required to be in order.

t = [
    [2, 20],
    [0, 0],
    [1, 10],
    [3, 20]
];

echo(lookup(1.5, t));

You can rearrange the entries all you like, and the result is still 15
because it finds the "1" entry and the "2" entry and interpolates
between them.

On 10/4/2023 6:21 PM, oz.at.michael@gmail.com wrote: > > Note that interpolation was always the intent of lookup(), judging by > the original examples. Search() is for searching. > It's not the interpolation that we're being surprised by. It's the fact that the entries aren't required to be in order. t = [ [2, 20], [0, 0], [1, 10], [3, 20] ]; echo(lookup(1.5, t)); You can rearrange the entries all you like, and the result is still 15 because it finds the "1" entry and the "2" entry and interpolates between them.

RD

Revar Desmera

Thu, Oct 5, 2023 1:33 AM

Perhaps we could add a ordered=true flag argument to lookup() that could tell it that it can do a binary search of the table, and if it stumbles on an out of order entry it can assert an error.

Revar

Perhaps we could add a `ordered=true` flag argument to `lookup()` that could tell it that it can do a binary search of the table, and if it stumbles on an out of order entry it can assert an error. - Revar

RD

Revar Desmera

Sat, Oct 7, 2023 11:27 PM

On Oct 4, 2023, at 2:53 PM, Revar Desmera revarbat@gmail.com wrote:

These changes should be fairly trivial to implement. I'd do it myself, but my submissions have had a 0% acceptance rate into the mainline code, so far.

I take this statement back. In looking though the OpenSCAD dev release sources, it seems like object() and has_key() made it into the code. 🎉🎊🍾

As an aside, roof() is a neat experimental feature. It still has a bug or two using method="voronoi", though:

include <BOSL2/std.scad>
roof(method="voronoi") star(n=5, step=2, d=20);

ERROR: Skeleton computation error. /Users/distiller/project/src/geometry/roof_vd.cc line 140: error in parabolic arc discretization in file foo.scad, line 8 <8,/Users/gminette/Documents/OpenSCAD/libraries/BOSL2/foo.scad>

Revar

> On Oct 4, 2023, at 2:53 PM, Revar Desmera <revarbat@gmail.com> wrote: > > These changes should be fairly trivial to implement. I'd do it myself, but my submissions have had a 0% acceptance rate into the mainline code, so far. I take this statement back. In looking though the OpenSCAD dev release sources, it seems like `object()` and `has_key()` made it into the code. 🎉🎊🍾 As an aside, `roof()` is a neat experimental feature. It still has a bug or two using method="voronoi", though: include <BOSL2/std.scad> roof(method="voronoi") star(n=5, step=2, d=20); ERROR: Skeleton computation error. /Users/distiller/project/src/geometry/roof_vd.cc line 140: error in parabolic arc discretization in file foo.scad, line 8 <8,/Users/gminette/Documents/OpenSCAD/libraries/BOSL2/foo.scad> - Revar

discuss@lists.openscad.org

Proposed lookup() enhancements.