[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Evolution & optimization of the module system
From: |
Kevin Ryde |
Subject: |
Re: Evolution & optimization of the module system |
Date: |
Thu, 22 Feb 2007 09:21:46 +1100 |
User-agent: |
Gnus/5.110006 (No Gnus v0.6) Emacs/21.4 (gnu/linux) |
address@hidden (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.
- Evolution & optimization of the module system, Ludovic Courtès, 2007/02/17
- Re: Evolution & optimization of the module system, Kevin Ryde, 2007/02/18
- Re: Evolution & optimization of the module system, Ludovic Courtès, 2007/02/19
- Re: Evolution & optimization of the module system,
Kevin Ryde <=
- Re: Evolution & optimization of the module system, Ludovic Courtès, 2007/02/22
- Re: Evolution & optimization of the module system, Kevin Ryde, 2007/02/22
- Re: Evolution & optimization of the module system, Ludovic Courtès, 2007/02/23
- Re: Evolution & optimization of the module system, Kevin Ryde, 2007/02/25
- Re: Evolution & optimization of the module system, Ludovic Courtès, 2007/02/26
- Re: Evolution & optimization of the module system, Kevin Ryde, 2007/02/26
- Re: Evolution & optimization of the module system, Ludovic Courtès, 2007/02/27