Hi Lindsay,
> As part of getting a handle on OO in picolisp I implemented a basic
> arithmetic coder.
> This is just the Coder and a simple adaptive model.
>
> https://github.com/thinknlive/picolisp-acdc
Cool! Looks good (Though I didn't try to understand the details).
> It is slower than I expected it to be, but I was focused more on getting
> the implementation correct in this pass.
>
> Any optimization suggestions welcome. Maybe not use OO at all and leverage
> namespaces.
Though the method lookup in OO slows things down theoretically, I don't think it
matters here.
: (bench (ACDC_Compress (need (** 2 16) (char "A"
2.717 sec
-> (0 1 0 0 0 0 0 0 1 ...
I should explain that there is a way in PicoLisp to profile programs. This is
not really documented, but the 'prof' function in @lib/prof.l is analog to
'debug' or 'trace'. You call it on the functions and methods you are interested
in. Because 'ACDC_Compress' calls 'emit>', 'update> etc. I did:
(load "@lib/prof.l")
(mapc prof
(quote
ACDC_Compress
(emit> . +ACDC_BasicModel)
(update> . +ACDC_BasicModel)
(emitEof> . +ACDC_BasicModel)
(computeLower> . +ACDC_BasicModel) ) )
: (bench (ACDC_Compress (need (** 2 16) (char "A" T
2.703 sec
-> T
and then call 'profile':
: (profile)
(384 13 computeLower> . +ACDC_BasicModel)
(114 1 emit> . +ACDC_BasicModel)
(17 1 update> . +ACDC_BasicModel)
(9 0 ACDC_Compress)
(0 0 emitEof> . +ACDC_BasicModel)
-> (0 0 emitEof> . +ACDC_BasicModel)
The numbers in the CAR indicate ticks (see (doc 'ticks))
Now we know that 'computeLower>' takes most of the time. As this method does
massive idx lookups, the efficiency of that tree comes to mind. I stopped at a
breakpoint, and did
! (cons (depth (: counts)) @@)
-> ((130 . 37) . 258)
and notice that this tree is not optimally balanced.
Looking at the 'T' method, I see that
(let (Tmp NIL) # use idx tree for model probabilities
(for X (: max) (idx 'Tmp (list (dec X) 1) T))
(balance 'Tmp Tmp)
(=: counts Tmp) )
the usage of 'balance' is not correct. 'balance' does not take an idx tree, but
a sorted list. So I changed these lines to
(balance
(:: counts)
(make (for X (: max) (link (list (dec X) 1 )
and ran it again:
1.364 sec
(73 5 computeLower> . +ACDC_BasicModel)
(48 4 emit> . +ACDC_BasicModel)
(3 0 update> . +ACDC_BasicModel)
(3 0 ACDC_Compress)
(0 0 emitEof> . +ACDC_BasicModel)
Doubled the speed :)
Perhaps there are other bottlenecks?
♪♫ Alex
--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
