Re: Digging into Symbols

2020-04-28 Thread Wilhelm Fitzpatrick

On 4/28/20 2:18 AM, Guido Stepken wrote:


E.g Python dqueue doesn't show any performance loss here


The performance of a particular python data structure has no bearing on 
the fact that your original statement:



In most Lisp languages, you only can "append" to a list, never "prepend"
..is incorrect on its face, since the cons based linked list is the 
fundamental data structure of Lisp and _prefers_ prepend over append.



--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe


Re: Digging into Symbols

2020-04-28 Thread John Duncan
It’s hard to predict cache behavior without an actual workload, so i would
recommend using cachegrind with a real program (not a benchmark) to
evaluate the cost of doing things one way or the other.

On Tue, Apr 28, 2020 at 05:24 Guido Stepken  wrote:

> Certainly. But how is it *implemented* internally? Mostly you suffer
> massive performance loss when prepending, because complete linked list gets
> moved to a new place in memory. If internal representaion ist a double
> cell, one value, pointer to next, then you quickly suffer CPU cache misses.
> Wild jumps across memory with upto 18 CPU waitstates for random access.
> Means: Your proud 4 GHz machine gets slower than a 250 MHz embedded ESP32
> ARM CPU. E.g Python dqueue doesn't show any performance loss here.
>
> Have fun!
>
> Am Dienstag, 28. April 2020 schrieb Wilhelm Fitzpatrick :
> > On 4/27/20 2:42 PM, Guido Stepken wrote:
> >
> >> In most Lisp languages, you only can "append" to a list, never
> "prepend".:
> >
> > "Prepend", aka "add to the beginning" seems the natural (and
> non-destructive) operation of Lisp, e.g.
> >
> > (cons 9 (1 2 3)) -> (9 1 2 3)
> >
> > ..perhaps that is what you meant?
> >
> > -wilhelm
> >
> >
> > --
> > UNSUBSCRIBE: mailto:picolisp@software-labde 
> ?subject=Unsubscribe
> >

-- 
John Duncan


Re: Digging into Symbols

2020-04-28 Thread Guido Stepken
Certainly. But how is it *implemented* internally? Mostly you suffer
massive performance loss when prepending, because complete linked list gets
moved to a new place in memory. If internal representaion ist a double
cell, one value, pointer to next, then you quickly suffer CPU cache misses.
Wild jumps across memory with upto 18 CPU waitstates for random access.
Means: Your proud 4 GHz machine gets slower than a 250 MHz embedded ESP32
ARM CPU. E.g. Python dqueue doesn't show any performance loss here.

Have fun!

Am Dienstag, 28. April 2020 schrieb Wilhelm Fitzpatrick :
> On 4/27/20 2:42 PM, Guido Stepken wrote:
>
>> In most Lisp languages, you only can "append" to a list, never
"prepend".:
>
> "Prepend", aka "add to the beginning" seems the natural (and
non-destructive) operation of Lisp, e.g.
>
> (cons 9 (1 2 3)) -> (9 1 2 3)
>
> ..perhaps that is what you meant?
>
> -wilhelm
>
>
> --
> UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
>


Re: Digging into Symbols

2020-04-27 Thread Alexander Burger
On Mon, Apr 27, 2020 at 02:38:35PM -0700, Wilhelm Fitzpatrick wrote:
> > Correct. The first character(s) need to be accessed more prominently.
> > 
> Hmm... because checking the first
> byte/character is just a mask, rather than
> shift & mask?

Yes, but most of all it concerns the first up to 8 characters in the first
*cell* of the name.

☺/ A!ex

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe


Re: Digging into Symbols

2020-04-27 Thread Wilhelm Fitzpatrick

On 4/27/20 2:42 PM, Guido Stepken wrote:


In most Lisp languages, you only can "append" to a list, never "prepend".:


"Prepend", aka "add to the beginning" seems the natural (and 
non-destructive) operation of Lisp, e.g.


(cons 9 (1 2 3)) -> (9 1 2 3)

..perhaps that is what you meant?

-wilhelm


--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe


Re: Digging into Symbols

2020-04-27 Thread Guido Stepken
In most Lisp languages, you only can "append" to a list, never "prepend".

Python, e.g., has such structures:
https://www.geeksforgeeks.org/deque-in-python/

The "*d*ouble *e*nded *queue*". Appending, prepending, Python simply lets
you do, what you want! ;-)

Mighty, mighty stuff, highly efficient!

Have fun!

Am Montag, 27. April 2020 schrieb Wilhelm Fitzpatrick :
> I've been digging down to really understand the symbol implementation in
Picolisp, since symbols are used for so many purposes within the language.
>
> One surprising thing I learned last night is that (get ...) has a side
effect! It moves the key that was accessed to the head of the symbol
"tail". I assume this is a performance optimization to cause recently
accessed properties to "bubble up" to the front of the list in case they
are re-accessed soon.
>
> A few questions:
>
> 1. I understand why (cdr) doesn't function on a symbol (semantically it's
not a pair) but I'm curious why (car) is allowed to work (returning the
VAL)?
>
> 2. Is there anyway within the REPL to inspect the tail structure of the
symbol directly? This is mostly from curiosity.
>
> 3. Again from curiosity, I'm wondering why the bytes of the name are
seemingly stored "backwards"? I'm assuming this also provides some
performance optimization.
>
> -wilhelm
>
>
> --
> UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
>


Re: Digging into Symbols

2020-04-27 Thread Wilhelm Fitzpatrick

Thanks for the insights, Alex!

On 4/27/20 1:53 PM, Alexander Burger wrote:

This means, a pointer to a cell points direcly to its CAR, while a pointer to a
symbol points to its VAL. In both cases (car ...) or (val ...) are just a single
pointer derefernces (memory fetches).
Ah, so car and val are effectively synonyms, and it's easier to allow 
that then prevent :)



3. Again from curiosity, I'm wondering why the
bytes of the name are seemingly stored
"backwards"? I'm assuming this also provides
some performance optimization.

Correct. The first character(s) need to be accessed more prominently.

Hmm... because checking the first byte/character is just a mask, rather 
than shift & mask?


-wilhelm


--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe


Re: Digging into Symbols

2020-04-27 Thread Henry Baker
The "move-to-front" heuristic is equivalent to the LRU caching policy.

The "move-up-by-one" heuristic converges to LFU (least frequently used) caching 
policy.

Perhaps LFU is what you really want?

BTW, "move-up-by-one" has a side-effect on every invocation, as does 
"move-to-front".
However, you can do "move-up-by-one" only every 1/N times, and still converge 
to LFU.

At 12:55 PM 4/27/2020, Wilhelm Fitzpatrick wrote:
>I've been digging down to really understand the symbol implementation in 
>Picolisp, since symbols are used for so many purposes within the language.
>
>One surprising thing I learned last night is that (get ...) has a side effect! 
>It moves the key that was accessed to the head of the symbol "tail". I assume 
>this is a performance optimization to cause recently accessed properties to 
>"bubble up" to the front of the list in case they are re-accessed soon.
>
>A few questions:
>
>1. I understand why (cdr) doesn't function on a symbol (semantically it's not 
>a pair) but I'm curious why (car) is allowed to work (returning the VAL)?
>
>2. Is there anyway within the REPL to inspect the tail structure of the symbol 
>directly? This is mostly from curiosity.
>
>3. Again from curiosity, I'm wondering why the bytes of the name are seemingly 
>stored "backwards"? I'm assuming this also provides some performance 
>optimization.
>
>-wilhelm
>
>-- 
>UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe


-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe



Re: Digging into Symbols

2020-04-27 Thread Alexander Burger
Hi Wilhelm,

> that (get ...) has a side effect! It moves the
> key that was accessed to the head of the
> symbol "tail". I assume this is a performance
> optimization to cause recently accessed
> properties to "bubble up" to the front of the
> list in case they are re-accessed soon.

Yes, exactly.


> 1. I understand why (cdr) doesn't function on
> a symbol (semantically it's not a pair) but
> I'm curious why (car) is allowed to work
> (returning the VAL)?

This is a result of the pointer structure of PicoLisp. As you may know (from
e.g. doc64/structures), a cell is

  |
  V
  +-+-+
  | CAR | CDR |
  +-+-+

while a symbol is

|
V
  +-+-+
  | | VAL |
  +--+--+-+

This means, a pointer to a cell points direcly to its CAR, while a pointer to a
symbol points to its VAL. In both cases (car ...) or (val ...) are just a single
pointer derefernces (memory fetches).



> 2. Is there anyway within the REPL to inspect
> the tail structure of the symbol directly?

It is in fact possible, with some tricky pointer arithmetics:

   : (put 'A 'a 1)
   -> 1
   : (put 'A 'b 2)
   -> 2
   : (val (adr (abs (adr 'A
   -> ((2 . b) (1 . a) . 65)



> 3. Again from curiosity, I'm wondering why the
> bytes of the name are seemingly stored
> "backwards"? I'm assuming this also provides
> some performance optimization.

Correct. The first character(s) need to be accessed more prominently.

☺/ A!ex

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe



Digging into Symbols

2020-04-27 Thread Wilhelm Fitzpatrick
I've been digging down to really understand the symbol implementation in 
Picolisp, since symbols are used for so many purposes within the language.


One surprising thing I learned last night is that (get ...) has a side 
effect! It moves the key that was accessed to the head of the symbol 
"tail". I assume this is a performance optimization to cause recently 
accessed properties to "bubble up" to the front of the list in case they 
are re-accessed soon.


A few questions:

1. I understand why (cdr) doesn't function on a symbol (semantically 
it's not a pair) but I'm curious why (car) is allowed to work (returning 
the VAL)?


2. Is there anyway within the REPL to inspect the tail structure of the 
symbol directly? This is mostly from curiosity.


3. Again from curiosity, I'm wondering why the bytes of the name are 
seemingly stored "backwards"? I'm assuming this also provides some 
performance optimization.


-wilhelm


--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe