Re: Refactor get/set_property to take the item as first argument (issue 573670043 by address@hidden)

[Han-Wen Nienhuys]

On Thu, Apr 9, 2020 at 7:45 PM <address@hidden> wrote:
>
> On 2020/04/09 17:07:46, hanwenn wrote:
> > I'm curious about these optimizations. Can you say more?
>
> Properties are currently stored in alists.  They can be stored in
> vectors instead.  Give all grob properties a number, then have an array
> per grob type mapping this number to an index into an array.  The first
> number can be memoized for literal property names, turning a property
> lookup into two indexing operations.
>
> That's the gist.  For Scheme code, the memoization could be replaced by
> macro compilation, but Guilev2 byte compilation of course is sort of a
> roadblock here, too.

I think it is a great idea to store properties in vectors rather than
alists. They take up less space, and lookups are faster.

Your specific approach sounds very laborious, and I see many
downsides, for example:

* this will make it hard to add new grob-properties at runtime

* memory use: each SCM value takes 8 bytes, and there are 416 grob
properties today, for a total of 3328 bytes. Morgenlied is single page
of music and has 3704 grobs. So storage for the vectors (which will be
mostly empty) will take up 12M / page. This likely will result in
doubling the memory use of LilyPond.

* Let's not put another roadblock in front of GUILE v2 adoption.

Have you considered building a custom hash table for the properties?
We could construct a table based on probing (so we don't need buckets
which would reintroduce linked lists). Since symbols have unique
addresses, we could do the hashing by casting SCM to uintptr and
hashing a uint64 down to the table size. This means we'll still do the
uint64 -> index on each lookup, but it's likely much faster than
walking alists, and would cut memory for properties in half.

We could experiment with this without requiring a giant rewrite of the
source code.

-- 
Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen