Glib algorithms #2436 vote
Gary Furnish
Multiplatform threads
Thread pools
Asynchronous Queues
Memory Slices
Doubly and Singly linked lists
Queues
Sequences
Hash Tables
Arrays
Balanced Binary Trees
N-ary Trees
Quarks
In particular it features a slab memory allocator based on:
http://citeseer.ist.psu.edu/bonwick94slab.html
http://citeseer.ist.psu.edu/bonwick01magazines.html
The documentation for glib is found at http://library.gnome.org/devel/glib/2.14/glib-Memory-Slices.html
The files are all GPL 2.0 or greater. Although glib normally has
extensive dependencies, all of them have been removed, as have parts
of glib that are not strictly algorithms (such as string parsing). To
avoid autoconf/make troubles, the new parallel build system currently
in experimental testing features a simple, elegant python autoconf
replacement. The extra build time for libcsage is minimal, and wall
time often decreases due to the new parallel build system. Finally,
until testing is complete, parallel build and glib are orthogonal and
can exist in parallel to all existing Sage code, making review
significantly easier.
Right now there are no easy to use C libraries included with sage.
Using c++ stl requires extremely painful Cython wrapping. Therefore
everywhere pure performance is needed, ad hoc solutions are often used
(see integer.pyx, etc), which often introduce subtle and painful
bugs. Furthermore there are many places in Sage that could benefit
from a unified slab allocator (as opposed to a pool which can only
grow). Finally the extensive symbolics modifications I am working on
make use of glib (especially trees and lists) to enable very fast
symbolic manipulations. By using glib algorithms I avoid having to
roll my own code that would require extensive manual review and
debugging. This code drop is big enough that Mabshoff would like a
formal +1 vote, and I'd be happy to address any concerns.
Mar 25 00:00:13 <mabshoff> yes. It isn't an spkg, but the code drop is
large enought to warrent a vote.
Mar 25 00:00:21 <mabshoff> You can quote me on that.
Mar 25 00:00:35 <mabshoff> You should say *why* it is a good idea and
*what* goodies it does provide.
Mar 25 00:00:59 <mabshoff> Since it will only become useful after the
switch to pbuild and doesn't
Mar 25 00:01:21 <mabshoff> harm anything with the old build it also
doesn't have an impact on the current
Mar 25 00:01:24 <mabshoff> codebase.
Mar 25 00:01:31 <mabshoff> You can quote me on that, too.
--Gary
mabshoff
On Mar 26, 1:12 am, Gary Furnish <gfurn...@gfurnish.net> wrote:
> Trac #2436 adds the following algorithms from glib to libcsage:
> Multiplatform threads
> Thread pools
> Asynchronous Queues
> Memory Slices
> Doubly and Singly linked lists
> Queues
> Sequences
> Hash Tables
> Arrays
> Balanced Binary Trees
> N-ary Trees
> Quarks
>
> The documentation for glib is found athttp://library.gnome.org/devel/glib/2.14/glib-Memory-Slices.html
pbuild patch [mostly on Linux so far] and I am convinced that the glib
subset Gary cut out will be very useful.
Cheers,
Michael
boo...@u.washington.edu
On Tue, 25 Mar 2008, Gary Furnish wrote:
>
> Trac #2436 adds the following algorithms from glib to libcsage:
> Multiplatform threads
> Thread pools
> Asynchronous Queues
> Memory Slices
> Doubly and Singly linked lists
> Queues
> Sequences
> Hash Tables
> Arrays
> Balanced Binary Trees
> N-ary Trees
> Quarks
+1, I can use this to speed up the polynomial evaluation code.
Mike Hansen
--Mike
Martin Albrecht
> Trac #2436 adds the following algorithms from glib to libcsage:
> Multiplatform threads
> Thread pools
> Asynchronous Queues
> Memory Slices
> Doubly and Singly linked lists
> Queues
> Sequences
> Hash Tables
> Arrays
> Balanced Binary Trees
> N-ary Trees
> Quarks
I am all for that, so +1.
> In particular it features a slab memory allocator based on:
> http://citeseer.ist.psu.edu/bonwick94slab.html
> http://citeseer.ist.psu.edu/bonwick01magazines.html
> The documentation for glib is found at
> http://library.gnome.org/devel/glib/2.14/glib-Memory-Slices.html The files
> are all GPL 2.0 or greater. Although glib normally has
> extensive dependencies, all of them have been removed, as have parts
> of glib that are not strictly algorithms (such as string parsing). To
> avoid autoconf/make troubles, the new parallel build system currently
> in experimental testing features a simple, elegant python autoconf
> replacement. The extra build time for libcsage is minimal, and wall
> time often decreases due to the new parallel build system. Finally,
> until testing is complete, parallel build and glib are orthogonal and
> can exist in parallel to all existing Sage code, making review
> significantly easier.
> Right now there are no easy to use C libraries included with sage.
> Using c++ stl requires extremely painful Cython wrapping. Therefore
> everywhere pure performance is needed, ad hoc solutions are often used
> (see integer.pyx, etc), which often introduce subtle and painful
> bugs.
This was already discussed at
http://groups.google.com/group/sage-devel/browse_thread/thread/a25146f45a5c6b97/3e996f8485802a01
and IMHO the outcome was that it is unclear whether GLIB can improve the
integer.pyx experience. There is a reason integer.pyx looks like it does
(avoiding going up the inheritance tree etc.).
> Furthermore there are many places in Sage that could benefit
> from a unified slab allocator (as opposed to a pool which can only
> grow).
Sage already ships several Slab allocators: PyMem_Malloc, OMalloc, Givaro's
slab allocator etc. Sure Sage could use those more but adding another slab
allocator won't help, unless:
- it is easier to debug, develop with, enable/disable, etc and/or
- it offers better performance.
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
Robert Miller
> Trac #2436 adds the following algorithms from glib to libcsage:
> Multiplatform threads
> Thread pools
> Asynchronous Queues
> Memory Slices
> Doubly and Singly linked lists
> Queues
> Sequences
> Hash Tables
> Arrays
> Balanced Binary Trees
> N-ary Trees
> Quarks
William Stein
How difficult will it be to update our version whenever upstream
changes? Do only you know how to do this?
Why put this in c_lib instead of a separate spkg called glib-min?
Couldn't such a package be useful outside of sage?
Any chance the glib people might see this as a "fork"?
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
mabshoff
> How difficult will it be to update our version whenever upstream
> changes? Do only you know how to do this?
> Why put this in c_lib instead of a separate spkg called glib-min?
> Couldn't such a package be useful outside of sage?
> Any chance the glib people might see this as a "fork"?
dependencies. If the glib people would provide a stripped down
version of glib we should switch.
Cheers,
Michael
William Stein
<Michael...@mathematik.uni-dortmund.de> wrote:
>
>
>
> On Mar 26, 6:02 pm, "William Stein" <wst...@gmail.com> wrote:
> > Is any of the code gpl v3+ only?
>
> No.
That's good.
>
>
> > How difficult will it be to update our version whenever upstream
> > changes? Do only you know how to do this?
>
> Not particularly hard.
You didn't answer my second question.
> > Why put this in c_lib instead of a separate spkg called glib-min?
> > Couldn't such a package be useful outside of sage?
>
> It is easiest if we put it into libcsage.
That's not a good enough answer. Until now almost all code in libcsage and
the main sage library has been new code we've written -- except a few
exceptions,
where we greatly regretted them greatly and moved the code out later.
So from experience I'm very opposed to this code being in c_lib.
I vote -1 to this code going into sage unless:
(1) it is put in a separate spkg, and
(2) the process of extracting glib-min from the official glib
tarball is automated.
-- William
mabshoff
On Mar 26, 6:43 pm, "William Stein" <wst...@gmail.com> wrote:
> On Wed, Mar 26, 2008 at 10:09 AM, mabshoff
>
>
> > On Mar 26, 6:02 pm, "William Stein" <wst...@gmail.com> wrote:
> > > Is any of the code gpl v3+ only?
>
> > No.
>
> That's good.
>
>
>
> > > How difficult will it be to update our version whenever upstream
> > > changes? Do only you know how to do this?
>
> > Not particularly hard.
>
> You didn't answer my second question.
documented. I don't consider such a thing "hard" once it has been
documented.
> > > Why put this in c_lib instead of a separate spkg called glib-min?
> > > Couldn't such a package be useful outside of sage?
>
> > It is easiest if we put it into libcsage.
>
> That's not a good enough answer. Until now almost all code in libcsage and
> the main sage library has been new code we've written -- except a few
> exceptions,
> where we greatly regretted them greatly and moved the code out later.
> So from experience I'm very opposed to this code being in c_lib.
>
> I vote -1 to this code going into sage unless:
> (1) it is put in a separate spkg, and
> (2) the process of extracting glib-min from the official glib
> tarball is automated.
will break in the next release in six months and writing automated
tools will take longer than actually doing the work in the first
place.
> -- William
Cheers,
Michael
didier deshommes
How frequent are the glib releases? If they're not that frequent, this
should less than an issue as long as Gary documents what he's done
somewhere :)
didier
>
> > -- William
>
> Cheers,
>
> Michael
>
>
> >
>
William Stein
If you've been maintaining packages for Sage for three years, and expect
to be maintaining them for years to come, you'de view this as a much
bigger deal. It's really bad when there is a big chunk of code in Sage
that gets out of stream with "up stream", but no easy way to resolve that
problem.
-- William
Gary Furnish
Most of the bloat in glib is internationaliztaion, which is not included in this patch. The parts that are included are simple enough and well documented enough (either in the code or in glib documents) that anyone should be able to easily maintain it. Furthermore, I intend to help maintain the C algorithms. I fully intend to work on them actively if their speed is not sufficient. Making a seperate spkg dramatically increases the difficulty of active development.
Robert Bradshaw
> Honestly, independent of the spkg vs libcsage issue, which is
> really an issue of semantics in my opinion, Sage has no high speed
> implementations of C algorithms. Sage can not escape this forever.
> Either someone will have to write their own at some point or we can
> use glib as a starting block. It is a big chunk of code, but Sage
> needs fast lists, hash tables, etc. Using glib as a starting point
> dramatically reduces debugging time, and is therefore preferable.
Browsing the glib documentation, looking at its features, and reading
what other people have to say about it I think this is a worthy set
of things to include.
One question I have is how much faster glib hashtables are than
python dictionaries (as accessed directly through the Python/C API,
which they will be from Cython if declared as type "dict") and how
much faster glib (linked or non-linked) lists are then Python lists.
Have you run any tests? If there is not a significant speed
difference, it would be preferable to use the Python datatypes to
store Python objects when possible (for cleaner code and to minimize
recounting woes). This wouldn't mean that glib isn't worth including
however.
> I don't see how blocking a glib patch because of maintenance issues
> really helps solve this problem in the long run. Is it really
> preferable that I code up custom versions of the things so that I
> can have fast symbolic implementations?
No. I think the point is that before including it we should consider
issues of maintenance and this may influence where we put it. (Much
easier, for instance, than trying to move it later.) I agree that it
should probably be a seperate spkg.
> Most of the bloat in glib is internationaliztaion, which is not
> included in this patch. The parts that are included are simple
> enough and well documented enough (either in the code or in glib
> documents) that anyone should be able to easily maintain it.
> Furthermore, I intend to help maintain the C algorithms. I fully
> intend to work on them actively if their speed is not sufficient.
> Making a seperate spkg dramatically increases the difficulty of
> active development.
I agree that making an spkg raises the barrier of working on it, but
not by that much. Also, as an spkg, other components of Sage can make
use of it, and I think it will be much easier to keep in sync with
and contribute upstream.
I'd also really like to avoid a fork, which is what this could easily
turn into. I'm noticing a lot of changes from glib 2.16.1 at GNOME.
Is this the version you started from? Are you simply copying a subset
of the c/h files, or are there significant changes that need to be
done every time glib is updated (every month or two looking at the
history)?
I would like to see this included, but I think these issues need to
be resolved now, or they never will until it hurts us.
- Robert
Gary Furnish
I have not yet benchmarked hash tables (nor actually tried them out), but one of the big advantages is that they avoid much of the memory management issues, so I don't expect them to be slower (and if they are, I may have to fix that).
William Stein
>
> On Mar 26, 2008, at 11:57 AM, Gary Furnish wrote:
>
>> Honestly, independent of the spkg vs libcsage issue, which is
>> really an issue of semantics in my opinion, Sage has no high speed
>> implementations of C algorithms. Sage can not escape this forever.
>> Either someone will have to write their own at some point or we can
>> use glib as a starting block. It is a big chunk of code, but Sage
>> needs fast lists, hash tables, etc. Using glib as a starting point
>> dramatically reduces debugging time, and is therefore preferable.
>
> Browsing the glib documentation, looking at its features, and reading
> what other people have to say about it I think this is a worthy set
> of things to include.
I have to strongly agree that I really want something with the feature
set of glib included, and that I don't think we have any business writing
it from scratch.
> One question I have is how much faster glib hashtables are than
> python dictionaries (as accessed directly through the Python/C API,
> which they will be from Cython if declared as type "dict") and how
> much faster glib (linked or non-linked) lists are then Python lists.
> Have you run any tests? If there is not a significant speed
> difference, it would be preferable to use the Python datatypes to
> store Python objects when possible (for cleaner code and to minimize
> recounting woes). This wouldn't mean that glib isn't worth including
> however.
This is certainly worth knowing.
I agree. And I don't think the above has been sufficiently
addressed yet.
Sorry to be a pain, but what you're proposing doing with glib is
almost the same as say taking the pyrex code and sticking it in
SAGE_ROOT/devel/sage/pyrex
under the main Sage hg repo. Doing that would amount to both
a fork and a maintenance problem. Even I didn't go that far
to entagle Pyrex with Sage when forking Pyrex.
I want to emphasize again that I strongly disagree with putting
all of glib-lite in SAGE_ROOT/devel/sage/, and I don't see
why doing that is going to make maintenance easier.
But I also want to emphasize that I strongly support glib-lite going
into Sage in some form, and I greatly greatly appreciate the hard
work you've put into making this possible.
-- William
William Stein
> Honestly, independent of the spkg vs libcsage issue, which is really an
> issue of semantics in my opinion, Sage has no high speed implementations of
> C algorithms. Sage can not escape this forever. Either someone will have
> to write their own at some point or we can use glib as a starting block. It
> is a big chunk of code, but Sage needs fast lists, hash tables, etc. Using
> glib as a starting point dramatically reduces debugging time, and is
> therefore preferable.
> I don't see how blocking a glib patch because of
> maintenance issues really helps solve this problem in the long run. Is it
> really preferable that I code up custom versions of the things so that I can
> have fast symbolic implementations?
I'm not trying to block the patch in order to solve the problem. I'm just hoping
to convince you that putting this code in libcsage is the wrong approach for
numerous reasons. That a "glib-lite" derivative of glib is best done as a separate
spkg, and that this has by far the best chance of living, being useful outside
of Sage, etc. Also, from my point of view almost _everybody_ involved in Sage has
come and gone, at one point or another, and I want *nothing* in Sage whose maintenance
depends on only one person. I'm scared of a bus factor of 1 for anything
in Sage.
> Most of the bloat in glib is internationaliztaion, which is not included in
> this patch. The parts that are included are simple enough and well
> documented enough (either in the code or in glib documents) that anyone
> should be able to easily maintain it.
That's very good to know.
> Furthermore, I intend to help
> maintain the C algorithms. I fully intend to work on them actively if their
> speed is not sufficient. Making a seperate spkg dramatically increases the
> difficulty of active development.
Why??? I could have said the same about Pyrex two years ago, and it would
have been silly. So could you please explain why this is true of glib-lite.
I'm not saying it isn't try! I just don't see why it should be. I know
you're extremely good at writing and arguing points, so please be patient
with me and explain why "Making a seperate spkg dramatically increases the
difficulty of active development." Again, I'm *not* at all sure I'm right!
And you've been much closer to that code than I am, so you're much more likely
to be right. That said, you've not given any argument, and this is the time
to work these things out -- that's why we have a vote, etc., for packages.
-- William
--
Robert Bradshaw
> I have not yet benchmarked hash tables (nor actually tried them
> out), but one of the big advantages is that they avoid much of the
> memory management issues, so I don't expect them to be slower (and
> if they are, I may have to fix that).
It is my understanding that Python dictionaries have been optimized a
lot, because in the end most of the speed of Python boils down to how
fast it can do dictionary lookups. I'm thinking specifically of the
case where keys and/or values are Python objects. (If they are not
then wrapping them can be a large overhead.) As for memory management
issues, if one is storing Python objects than this is actually a
bonus, otherwise one would have to do the memory management manually
(which is both error-prone and negates any savings).
- Robert
mabshoff
> > maintain the C algorithms. I fully intend to work on them actively if their
> > speed is not sufficient. Making a seperate spkg dramatically increases the
> > difficulty of active development.
>
> Why??? I could have said the same about Pyrex two years ago, and it would
> have been silly. So could you please explain why this is true of glib-lite.
> I'm not saying it isn't try! I just don't see why it should be. I know
> you're extremely good at writing and arguing points, so please be patient
> with me and explain why "Making a seperate spkg dramatically increases the
> difficulty of active development." Again, I'm *not* at all sure I'm right!
> And you've been much closer to that code than I am, so you're much more likely
> to be right. That said, you've not given any argument, and this is the time
> to work these things out -- that's why we have a vote, etc., for packages.
>
> -- William
>
lite in an spkg might be a little more work right now, but it forces
us [ehh Gary] to factor out the pbuild bits or write a makefile that
uses a bunch of env variables determined by spkg-install. Sticking
that in an spkg-install isn't that much work. Making the makefile
independent of pbuild would also increase the chances that other
projects would actually use the code.
Cheers,
Michael
Gary Furnish
William Stein
> I'll move this to an spkg.
With it moved to an spkg, I now vote +1, which makes it unanimous and official
that glib-lite goes into Sage (as an spkg).
-- William
--