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

Reply via email to