Re: Evolution & optimization of the module system

[Kevin Ryde <user42@zip.com.au>]

ludovic.courtes@laas.fr (Ludovic Courtès) writes:
>
> Actually, `process-duplicates' is O(N*USES) _for each module used_.  So
> the overall duplicate processing is really O(N*USES^2).  With the
> patched version, the whole process is O(N*USES).  That can make quite a
> difference when USES > 1.

It should be ok, it's only hash table lookups, which are fast.  And N
is normally pretty modest too.

> Right, it increases the size of individual module objects.  I haven't
> made any measurements but I'm not sure whether it should be a concern,
> given that the number of modules is not supposed to be too high (i.e.,
> at most a few hundreds).  Any idea of an estimate of the memory occupied
> by a (balanced) hash table given its number of elements?

Copying the table of 2000 core bindings into every module doesn't
sound good, not if it's only for once-off duplicates checking.  If you
want you can check the existing innermost loops are good.  In
process-duplicates var1 and var2 are almost always different (one of
them #f usually), so getting that down to C with some sort of
"hashq-intersection" or "hashq-for-each-intersection" would help a
lot.  I'd predict throwing a little C at bottlenecks like that will be
enough.

Another possibility would be to defer duplicates checking until the
end of a define-module or use-modules form (or even until the end of
the file), if mutual cross-checks can be done faster en-block, if you
know what I mean.  It could use a temporary combined hash if that
helped (perhaps sharing bucket cells to save gc work).  The particular
"module-define!" you struck should obviously be only about USES many
hash lookups (ie. about a dozen typically), most of the time, if
that's not already the case.

> Depends on what you mean here.  Modules distributed with core Guile are
> not special-cased (and shouldn't be, IMO).

They're special in that we know there's no clashes between them.
process-duplicates should ignore any ice-9 vs ice-9, if that doesn't
happen already.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel