guile-user
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Christopher Lam
Subject: Re: a C<->guile O(2N) problem
Date: Wed, 11 Dec 2019 14:47:55 +0000

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 <address@hidden>
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!
>


reply via email to

[Prev in Thread] Current Thread [Next in Thread]