a C<->guile O(2N) problem

a C<->guile O(2N) problem

[Christopher Lam]

Hello guilers

I am asking for some help optimizing C<->guile while working on the
simplest of lispy data structures; the proper list. The C equivalent being
used is glib's g_list.

In https://github.com/Gnucash/gnucash/blob/maint/common/base-typemaps.i#L142
these are converted via the simple but O(2*N) expensive
prepend-and-reverse, building SCM list by traversing g_list, and vice versa
for the return trip.

It came to light that if we could define the GList transform with CAR =
node->data and CDR = node->next; the C->SCM transform could be O(1)
efficient. There are issues about finding the correct SWIG converter for
node->data pointer dereferences, but this is a problem for another day.
With SCM->C transform, we don't anticipate long lists, so, the issue is
less acute, but it would be nice to optimise it too.

Does anyone have experience converting the above efficiently? Is this
something that would need ffi work?

Thanks for any help!

Re: a C<->guile O(2N) problem

[Christopher Lam]

Update: the solution turned out to be easy to do in swig, and actually not
that useful. Prepend-and-reverse to convert g_list to SCM list, for lists
tested up to 10e6, takes a fraction of a second.

https://github.com/Gnucash/gnucash/pull/620 was the proof-of-concept O(1)
GList->SplitListNode with benchmarks.


On Sun, 8 Dec 2019 at 13:15, Christopher Lam <christopher.lck@gmail.com>
wrote:

> Hello guilers
>
> I am asking for some help optimizing C<->guile while working on the
> simplest of lispy data structures; the proper list. The C equivalent being
> used is glib's g_list.
>
> In
> https://github.com/Gnucash/gnucash/blob/maint/common/base-typemaps.i#L142
> these are converted via the simple but O(2*N) expensive
> prepend-and-reverse, building SCM list by traversing g_list, and vice versa
> for the return trip.
>
> It came to light that if we could define the GList transform with CAR =
> node->data and CDR = node->next; the C->SCM transform could be O(1)
> efficient. There are issues about finding the correct SWIG converter for
> node->data pointer dereferences, but this is a problem for another day.
> With SCM->C transform, we don't anticipate long lists, so, the issue is
> less acute, but it would be nice to optimise it too.
>
> Does anyone have experience converting the above efficiently? Is this
> something that would need ffi work?
>
> Thanks for any help!
>