Re: [Chicken-users] I'm looking for suggestions regarding vectors vs. records vs. coops (again).

[Peter Bex]

On Sun, Jul 24, 2016 at 11:06:32AM -0700, Matt Welland wrote:
> For years now I've been using inlined vectors instead of records or coops
> for data structures due to performance concerns. Recently I was training
> someone on how to maintain my code and I felt quite lame explaining the
> vector records. So I started switching to defstruct records. However I've
> started to hit some performance issues and one factor seems to be the
> records (more work to do to confirm this).
> 
> Below is a simplistic benchmark comparing using inlined vectors, inlined
> vectors with a type check, defstruct and coops. Where performance matters
> using vectors or type checked vectors seems to help. The benchmark seems
> enough to hint to me to switch back to vectors - especially in cases where
> I'm slinging around 10's of thousands of records.

Hello Matt,

The reason for this is pretty simple: record types do not have inlineable
accessors.  This means that accessors (and constructors) will require
that they are invoked in full CPS context.  If you have a procedure which
calls such an accessor, it will always be split up into at least 2 C
functions.

This is because records have an API defined by the procedures which are
created by the define-record(-type)/defstruct macros; the objects
themselves do not contain enough information to have a generic accessor,
and when you're calling an accessor, the compiler doesn't know that it's
a record accessor.  Vectors, on the other hand, have a common interface:
they can be referenced by one and the same accessor: vector-ref.
This is inlineable in C, as C_i_vector_ref().  In the next version of
CHICKEN, we'll even be able to rewrite those directly to C_slot() if
the vector is of a known length and the index is within bounds.

> My question: can anyone offer insight into a better way to balance
> performance with elegance/flexibility of records?

Luckily, there's a simple solution.  Felix wrote a wonderful little egg
called "typed-records", which provides drop-in replacements for
define-record(-type) *and* defstruct which will emit specialisations
for records.

That is, if an object is known to be a record of the given type, the
accessor is rewritten to (##sys#slot <record> <slot>).

For instance, with (defstruct foo bar qux), (foo-qux x) is rewritten
to (##sys#slot x 2) if x is known to be of type (struct foo).
The only disadvantage of this is that if you change your definition
of a record, you'll need to recompile all the units that access these
records, because they've been inlined as numbered slot references.

Changing the sample code in your e-mail by simply replacing "defstruct"
in your "use" line with "typed-records" results in noticeable
performance improvement:

Using vectors
1.148s CPU time, 33162750 mutations, 0/2309 GCs (major/minor)
Using vectors (safe mode)
2.308s CPU time, 0.02s GC time (major), 49744125 mutations, 15/20266 GCs 
(major/minor)
Using defstruct
1.66s CPU time, 33162750 mutations, 5/11665 GCs (major/minor)
Using coops
20.608s CPU time, 0.628s GC time (major), 33162760 mutations, 960/231731 GCs 
(major/minor)

Before making that one-word replacement, it was:

Using vectors
1.112s CPU time, 33162750 mutations, 0/2309 GCs (major/minor)
Using vectors (safe mode)
2.34s CPU time, 0.02s GC time (major), 49744125 mutations, 15/20266 GCs 
(major/minor)
Using defstruct
4.224s CPU time, 0.012s GC time (major), 33162750 mutations, 36/40736 GCs 
(major/minor)
Using coops
20.572s CPU time, 0.608s GC time (major), 33162760 mutations, 938/231753 GCs 
(major/minor)

Not too bad, especially considering that typed-records is _safe_: it
will only perform the rewrites when the compiler can prove that the given
object is of the required type.

If it cannot, you can always add a check to your code like this:
(if (not (my-type? x)) (error "wrong type") (begin ...))
The use of a predicate will tell the compiler that in the else branch,
x can only be of the required type.

If you're using separate compilation, you need to remember to ask the
compiler to emit the type declarations to a file, and use that file while
compiling the users of the API.

Cheers,
Peter

signature.asc
Description: Digital signature