Auto-caching, memoizing

[luser droog]

I'm not getting the speed-up I expected from this memo-izing
fibonacci program. it'll do 1 to 20 in .5 seconds, but even
with a generous dictionary 1 to 25 takes 4.sthg seconds.

real 0m4.060s
user 0m3.671s
sys 0m0.061s

Norah@laptop ~
$ cat memo.ps
%!

<<
/pusherr { % /errname {handler} --> /errname {old-handler}
errordict 3 1 roll % d n p
3 copy pop get % d n p op
2 index exch 5 2 roll put
}

/poperr { % /errname {handler}
errordict 3 1 roll put
}
>> begin

/fibonacci {
DICT begin
/undefined {
pop
dup 2 sub fibonacci
exch 1 sub fibonacci
add
} pusherr 3 2 roll

load

3 1 roll poperr
end
} dup 0 100 dict dup <<
0 1
1 1
>> { put dup }forall pop put def

0 1 25 { fibonacci = } for

Norah@laptop ~
$ time gsnd -dBATCH memo.ps
GPL Ghostscript 9.19 (2016-03-23)
Copyright (C) 2016 Artifex Software, Inc. All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393

real 0m3.986s
user 0m3.593s
sys 0m0.061s

[luser droog]

On Wednesday, August 23, 2017 at 3:10:48 PM UTC-5, luser droog wrote:
> I'm not getting the speed-up I expected from this memo-izing
> fibonacci program. it'll do 1 to 20 in .5 seconds, but even
> with a generous dictionary 1 to 25 takes 4.sthg seconds.
>
> real 0m4.060s
> user 0m3.671s
> sys 0m0.061s
>

Umm... ignore the previous code ... if you can. Here's an improved
version which demonstrates the same thing. I feel like it should be
faster.


real 0m4.032s
user 0m3.686s

sys 0m0.061s

Norah@laptop ~
$ cat memo.ps
%!

<<
/pusherr { % /errname {handler} --> /errname {old-handler}
errordict 3 1 roll % d n p
3 copy pop get % d n p op
2 index exch 5 2 roll put
}

/poperr { % /errname {handler}
errordict 3 1 roll put
}

/memo-func {
{
DICT begin
/undefined { pop /default load exec } pusherr 3 2 roll

load
3 1 roll poperr
end
}

dup length array copy
dup 3 2 roll 0 exch put cvx
}
>> begin


/fib <<
0 1
1 1
/default { dup 2 sub fib exch 1 sub fib add }
>> 100 dict copy memo-func def

0 1 25 { fib = } for

real 0m3.920s
user 0m3.640s
sys 0m0.030s

[luser droog]

On Wednesday, August 23, 2017 at 3:33:07 PM UTC-5, luser droog wrote:
> On Wednesday, August 23, 2017 at 3:10:48 PM UTC-5, luser droog wrote:
> > I'm not getting the speed-up I expected from this memo-izing
> > fibonacci program. it'll do 1 to 20 in .5 seconds, but even
> > with a generous dictionary 1 to 25 takes 4.sthg seconds.
> >
> > real 0m4.060s
> > user 0m3.671s
> > sys 0m0.061s
> >
>
>
> Umm... ignore the previous code ... if you can. Here's an improved
> version which demonstrates the same thing. I feel like it should be
> faster.
>

OMG. Duh. It never updates the dict with new values.

[luser droog]

Here we go. Much better results now.


real 0m0.173s
user 0m0.077s

sys 0m0.061s

Norah@laptop ~
$ cat memo.ps
%!

<<
/pusherr { % /errname {handler} --> /errname {old-handler}
errordict 3 1 roll % d n p
3 copy pop get % d n p op
2 index exch 5 2 roll put
}

/poperr { % /errname {handler}
errordict 3 1 roll put
}

/memo-func {
{
DICT begin

/undefined { pop dup default dup 3 1 roll def } pusherr 3 2 roll

real 0m0.167s
user 0m0.109s
sys 0m0.030s

[luser droog]

On Wednesday, August 23, 2017 at 3:40:48 PM UTC-5, luser droog wrote:
> On Wednesday, August 23, 2017 at 3:38:55 PM UTC-5, luser droog wrote:
> > On Wednesday, August 23, 2017 at 3:33:07 PM UTC-5, luser droog wrote:
> > > On Wednesday, August 23, 2017 at 3:10:48 PM UTC-5, luser droog wrote:
> > > > I'm not getting the speed-up I expected from this memo-izing
> > > > fibonacci program. it'll do 1 to 20 in .5 seconds, but even
> > > > with a generous dictionary 1 to 25 takes 4.sthg seconds.
> > > >
> > > > real 0m4.060s
> > > > user 0m3.671s
> > > > sys 0m0.061s
> > > >
> > >
> > >
> > > Umm... ignore the previous code ... if you can. Here's an improved
> > > version which demonstrates the same thing. I feel like it should be
> > > faster.
> > >
> >
> > OMG. Duh. It never updates the dict with new values.
>
>
> Here we go. Much better results now.
>
>
> real 0m0.173s
> user 0m0.077s
> sys 0m0.061s
>

For the benefit of spectators, here's some additional commentary.

> Norah@laptop ~
> $ cat memo.ps
> %!

We start with two procedures /pusherr and /poperr which provide
the capability of stacking error handlers. They're a little weird
because they use the regular operand stack as the stack as well
as using the stack for argument passing. So /pusherr, after a
casual glance at the stack effect comment, might appear not to
do anything useful at all. But it installs the new handler given
as an argument and returns the old handler. And /poperr takes
an argument handler and simply installs it.

Don't worry. It /is/ confusing.

>
> <<
> /pusherr { % /errname {handler} --> /errname {old-handler}
> errordict 3 1 roll % d n p
> 3 copy pop get % d n p op
> 2 index exch 5 2 roll put
> }
>
> /poperr { % /errname {handler}
> errordict 3 1 roll put
> }
>

I probably could factor it to use /poperr in the code for /pusherr.
Or something internally complicated, maintaining a stack data structure,
in exchange for a cleaner interface... hmmm....

On to the meat, ...

> /memo-func {
> {
> DICT begin
> /undefined { pop dup default dup 3 1 roll def } pusherr 3 2 roll
> load
> 3 1 roll poperr
> end
> }
> dup length array copy
> dup 3 2 roll 0 exch put cvx
> }
> >> begin
>

If you've been following my other recent threads, the idea should
be familiar. It's generating a procedure body specified by the
template but with the DICT replaced by the dict argument.

The resulting procedure simply pushes the local dict (again this
should be familiar), then pushes an error handler for the /undefined
error, then just does `load`, and pops the handler and the dict.

The error handler calls the procedure named /default and saves
the input and output as a new definition in the local dict.

>
> /fib <<
> 0 1
> 1 1
> /default { dup 2 sub fib exch 1 sub fib add }
> >> 100 dict copy memo-func def
>
> 0 1 25 { fib = } for
>

And the usage. Pretty close to the textbook mathematical form, I think.

fib(x) = { 0 -> 1
| 1 -> 1
{ fib(x-2) + fib(x-1)

And it runs, produces good looking results, and pretty fast! Hurray!

[luser droog]

Here's an updated version which maintains an internal stack as lisp-like
linked-list. I think it makes the code much nicer to read by removing
the extra stack juggling. But it's a little slower than the stackwise
version according to naive testing. It allocates lots of 2- and 3- element
arrays for its data.

%!

<<
/errorstack null % [ {errordict/errname{handler}} null ]

/pusherr {
errordict 3 1 roll 3 copy pop 2 copy get % ed /n {new} ed /n {old}
3 array astore cvx errorstack 2 array astore /errorstack exch store
put
}

/poperr {
errorstack dup null ne {
aload pop /errorstack exch store
exec put
} if

}

/memo-func {
{
DICT begin
/undefined { pop dup default dup 3 1 roll def } pusherr

load

poperr
end
}
dup length array copy
dup 3 2 roll 0 exch put cvx
}
>> begin

/fib <<
0 1
1 1
/default { dup 2 sub fib exch 1 sub fib add }
>> 100 dict copy memo-func def

0 1 100 { fib = } for