Pool for padics

[xcaruso]

As discussed on zulip, we propose to implement a pool for p-adic numbers.

CC: @roed314 @saraedum @jdemeyer

Component: padics

Keywords: pool, padicIMA

Author: Xavier Caruso

Branch/Commit: u/caruso/pool @ 5e3d9cd

Issue created by migration from https://trac.sagemath.org/ticket/23722

[xcaruso]

Branch: u/caruso/pool

[xcaruso]

Commit: 083ddb9

[xcaruso]

comment:2

I attach a first rough implementation that works only for CR elements.

The speed up is about 50% (= 2 times faster) for Zp(p) when p is small.

---

New commits:

083ddb9

Implementation of a pool for CR elements

[videlec]

comment:3

1. If you intend to have such an option then the code would better be shared with Integer.

2. The most convenient by far would be to extend @freelib Cython decorator. Typically we might want to use it for most basic rings.

[sagetrac-git]

Changed commit from 083ddb9 to f318ad6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f318ad6

Memory leaks fixed

[xcaruso]

comment:5

Replying to @videlec:

1. If you intend to have such an option then the code would better be shared with Integer.

Probably. But the pool for Integer has additional optimizations.
Moreover, it uses global variables (instead of classes) and is then faster.

2. The most convenient by far would be to extend @freelib Cython decorator.

Well, in my implementation, the parent plays some role (we have access to the pool through the parent and may enable/disable the pool for different parents using the same element class). It seems to be difficult to introduce these features in the @freelib decorator since parents are typical to sage.

Typically we might want to use it for most basic rings.

Indeed. For now, I'm just testing this for padics but it works well.

[videlec]

comment:6

I justed posted a message on Cython mailing list https://groups.google.com/forum/#!topic/cython-users/Uh4JCzDdIsQ

[roed314]

comment:7

Very nice!

Some thoughts:

• We should probably wait a bit to see if anyone responds on the Cython list. If they are going to implement such a pool, great; otherwise I definitely think this is a feature worth having in Sage.
• As you pointed out on Zulip, self.prime_pow isn't set during __cinit__. Since it's not used in any of the current linkage files, I think it's fine removing it from the call. If we implement a linkage where it's needed, we can rethink the process with that example in mind.
• I like your mechanism for allowing the enabling and disabling of pools at the level of individual parents. Presumably we'll eventually have heuristics for when pools should be enabled (depending on p and prec_cap).
• I'm not completely sure about the reference counting code you've used (though I don't have any particular flaws in mind). We should make sure to test for memory leaks somehow.
• At what level should we add a Pool? I'm hesitant to add it to Parent (because there is a memory cost), but there isn't another obvious place. Perhaps we should raise this on sage-devel once the code on this ticket has progressed a bit?

Great work Xavier!

[jdemeyer]

comment:8

Replying to @videlec:

1. If you intend to have such an option then the code would better be shared with Integer.

Absolutely! This should not be specific to p-adics.

[jdemeyer]

comment:9

Also, it would be good to have a short write-up of what exactly this does (the current branch doesn't have much documentation) before continuing the discussion.

[jdemeyer]

comment:10

See also #17670 which I created a long time ago but never did anything with.

[xcaruso]

comment:11

Replying to @roed314:

Very nice!

Thanks :-)

• We should probably wait a bit to see if anyone responds on the Cython list. If they are going to implement such a pool, great; otherwise I definitely think this is a feature worth having in Sage.

Sure.
But as I mentioned above, my implementation is based on the parent (which is typical to Sage).

• As you pointed out on Zulip, self.prime_pow isn't set during __cinit__. Since it's not used in any of the current linkage files, I think it's fine removing it from the call. If we implement a linkage where it's needed, we can rethink the process with that example in mind.

If self.prime_pow is needed in this initialization, I think that we should seriously consider the option to have a pool for each parent.

I actually think that this could be an option in any case. Concretely pool_enable could take an attribute global; if it set to true, then the pool is shared with all other parents using the same type; otherwise, it is local to the parent. And the default could be True.

• I like your mechanism for allowing the enabling and disabling of pools at the level of individual parents. Presumably we'll eventually have heuristics for when pools should be enabled (depending on p and prec_cap).

Yes.

• I'm not completely sure about the reference counting code you've used (though I don't have any particular flaws in mind). We should make sure to test for memory leaks somehow.

Reference counting should be fine (hopefully).
The line o.ob_refcnt = 1 in the de-allocation prevents the object to be collected again and again.
The line o.ob_refcnt = 0 in the allocation is needed because the reference counting is incremented just after.

• At what level should we add a Pool? I'm hesitant to add it to Parent (because there is a memory cost), but there isn't another obvious place. Perhaps we should raise this on sage-devel once the code on this ticket has progressed a bit?

One possible solution: we create a new class ParentWithPool (inheriting from Parent) and let the parents that wants to implement a pool derive from this class. This won't affect other parents (and then will limit the number of bugs).

[xcaruso]

comment:12

Replying to @jdemeyer:

See also #17670 which I created a long time ago but never did anything with.

Oh, I've always thought that overriding __dealloc__ doesn't prevent the actual deallocation of memory but just allows the user to free properly extra allocated memory (just like a C destructor). Am I mistaken?

[jdemeyer]

comment:13

Replying to @xcaruso:

Well, in my implementation, the parent plays some role

I'm not convinced that it should. Ideally, the implementation should be as generic as possible, so the parent should not be involved.

[jdemeyer]

comment:14

Replying to @xcaruso:

Oh, I've always thought that overriding __dealloc__ doesn't prevent the actual deallocation of memory but just allow the user to free properly extra allocated memory (just like a C destructor). Am I mistaken?

I think you are right. Like I said, I wrote #17670 a long time ago and I'm not claiming that the ticket description of #17670 is correct.

[sagetrac-git]

Changed commit from f318ad6 to 78c11cd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e9f0e2a	Local and global pools
78c11cd	Added doctests

[roed314]

comment:16

The documentation and changes help. Here are some comments.

• I think that in Cython <long?> is not necessary, since long isn't a pointer. The problem occurs when you ask Cython to interpret a pointer to one extension type as a pointer to another, and then get invalid memory references.
• You added a _pool attribute to LocalGenericElement. Was this accidental? Aren't pools supposed to be stored on the parent?
• There are various typos in the documentation; I'll fix the ones I notice.

[roed314]

comment:17

Replying to @jdemeyer:

Replying to @xcaruso:

Well, in my implementation, the parent plays some role

I'm not convinced that it should. Ideally, the implementation should be as generic as possible, so the parent should not be involved.

The benefit of having the parent involved is that you can turn on the pool for p=5 when it's useful, and off for p=next_prime(10^400) when it's not.

If we can make pools available upstream in Cython, I think it's worth giving up this feature. But if we're just implementing it in Sage, I like Xavier's choice to attach it to the parent, since I don't see anything in Sage other than elements using a pool, and we do get the flexibility of varying the behavior by parent.

[jdemeyer]

comment:18

Replying to @roed314:

The benefit of having the parent involved is that you can turn on the pool for p=5 when it's useful, and off for p=next_prime(10^400) when it's not.

Obvious question: why do you assume that p is fixed? I.e. why couldn't an element with p=5 be stored in the pool and recycled with p=7?

[roed314]

comment:19

Replying to @jdemeyer:

Replying to @roed314:

The benefit of having the parent involved is that you can turn on the pool for p=5 when it's useful, and off for p=next_prime(10^400) when it's not.

Obvious question: why do you assume that p is fixed? I.e. why couldn't an element with p=5 be stored in the pool and recycled with p=7?

It certainly can. But for larger p the object creation time is not as relevant compared to arithmetic time, so the pool is less useful (and possibly not worth the memory cost).

I'm not strongly attached to the ability to enable and disable the pool at the level of individual parents, but I think it does provide some benefit.

[jdemeyer]

comment:20

Replying to @roed314:

It certainly can.

So then, there is again no reason to get the parent involved...

[xcaruso]

comment:21

Replying to @roed314:

Replying to @jdemeyer:

Obvious question: why do you assume that p is fixed? I.e. why couldn't an element with p=5 be stored in the pool and recycled with p=7?

It certainly can.

And actually it is (in my implementation): a given pool may be shared between different parents, and it's for now the default for p-adics.

[xcaruso]

comment:22

Replying to @jdemeyer:

Replying to @roed314:

It certainly can.

So then, there is again no reason to get the parent involved...

Yes, there is because you may want, in some specific cases, to have separated pools.

I agree that sharing the pool for Zp(5) and Zp(7) is certainly the right thing to do. But, on the other hand, disabling the pool for Zp(nextprime(10^400)) makes sense as well.

Also, one can imagine other classes where the data structure corresponding to some parameters are not compatible with the data structure to other parameters (for instance, if we want to implement a p-adic number as a flint p-adic, then I guess that a 5-adic number cannot be easily recycled to a 7-adic number). For these classes, it's useful to have separated pools according to the parent.

[jdemeyer]

comment:23

Replying to @xcaruso:

Also, one can imagine other classes where the data structure corresponding to some parameters are not compatible with the data structure to other parameters

Yes, I can "imagine" that. However, I feel that we should go for an implementation which is as generic as possible and which therefore would not involve something Sage-specific like a parent.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b66f892

Set correctly the parent in _test_new

[sagetrac-git]

Changed commit from 78c11cd to b66f892

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

33797b6

Move pool to the parent class

[sagetrac-git]

Changed commit from b66f892 to 33797b6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

76457e9	Small fix in doctest
0af2ee1	change wording: is_global -> local
6880f2a	Adjust reference counting to the pool (working version)
ce9b213	Change order of attribute in parent.pxd
84d7956	Fallback for deallocation
b96b57c	Use pool in coerce maps
5e3d9cd	Activate pools for all padics

[sagetrac-git]

Changed commit from 33797b6 to 5e3d9cd

[jdemeyer]

comment:27

In case it is not clear, let me mention that I disagree with several design choices made here (storing the pool in the parent is one of them).

I think that the Integer pool is a much better idea and I suggest to expand on that instead of reinventing a new (worse) pool implementation.

[xcaruso]

comment:28

Don't worry, I think I understood that you disagree :-).

I wanted to be sure that my approach will eventually work and it's the reason why I continued working on it (and then pushed it to the ticket).
I'm however happy to discuss design choices.

But, I'm afraid that I didn't understand well your point.
Could you explain for instance more why you don't like storing the pool in the parent? Is it "just" because it's not enough cythonic? Is there something more?

Could you detail more please what should be the features of a good pool (according to you)? I understand, I think, that it should be attached to a python type, it that right? Are you proposing to modify Cython and embed it in the PyTypeObject structure?
Besides, do you think that the pool should be resizable or not? Should we let to the user the possibility to enable/disable it? More generally, should the pool be accessible through special methods/commands?

[jdemeyer]

comment:29

Replying to @xcaruso:

Could you detail more please what should be the features of a good pool (according to you)?

That's actually an excellent question. In decreasing order of importance, a pool should:

1. Be robust (all code which currently works with the type should continue to work the same way if the type is implemented with a pool).

2. Be fast.

3. Be as generic as possible, i.e. work for any type.

4. Not require any special code to use the pool (i.e. no PY_NEW or PY_NEW_WITH_POOL).

5. Make it easy for developers to add a pool to their types.

Besides, do you think that the pool should be resizable or not? Should we let to the user the possibility to enable/disable it? More generally, should the pool be accessible through special methods/commands?

First of all, these are details: we should first get a good design and then think about this.

To answer the question: I don't think that such features would ever be used. So, you could add them, but why? Perhaps more interesting would be to get access to some statictics, like how full is the pool, how often does it overflow/underflow...

[xcaruso]

comment:30

Ok.

At some point, I've also tried to conceal all these requirements but I then had to give up because I couldn't see how to achieve in pure Cython (i.e. without modifying the Cython compiler).
Indeed, following the implementation of @freelist (i.e. custom the C code of the standard tp_new and tp_dealloc functions for each type for which a pool is enabled) clearly required to modify the Cython compiler. Another related but maybe less aggressive solution is the following: we write generic functions tp_new_with_pool and tp_dealloc_with_pool functions (and attach them to each relevant type). The issue is that this requires to store the address of the pool in some data structure attached to the type (typically the PyTypeObject structure) but there is no space left on this struct. So, we need to add a variable. (Another option would be to lookup in a global dictionary but I didn't consider this option because of efficiency.)

Moreover, as already discussed, these brute solutions are not that fine because they do not prevent the creation/deletion of extra allocated objects (as mpz integers in the case of padics). So there would eventually require extra work. Maybe splitting __cinit__ and __dealloc__ into
two parts as discussed here: https://groups.google.com/forum/#!topic/cython-users/Uh4JCzDdIsQ
Then, in any case, having an efficient pool will require to adapt the implementation of the underlying elements.

I'm not part of the community of Cython developers (I mean people who are developing Cython). It's the reason why I had preferred mode "cythonic" solutions. But if you (or someone else) think that you can come up with a working code following the previous lines in a reasonable time, it's of course fine with me.

Besides, I think that the implementation I proposed (where the pool is attached to the parent) has interesting features. For padics, it's really efficient (2 times faster for ZpCR, 3 times faster for ZpFM) and cheap to have a pool when p is small. But it is not when p is large: the gain of speed is not significant (less than 1%) and the pool is greedy in memory. Thus having the possibility to enable/disable the pool according to the parent seems nice to me. Of course, the user will not do it manually but this can be done automatically at the creation of the parent based on some heuristics.
In the same spirit, small pools are enough when manipulating a small amounts of variables (i.e. iterating a recursive sequence) but large pools are better otherwise (e.g. manipulating large matrices for instance). So the good size of the pool depends on applications and I think it's a good idea to let to the user the possibility to play with it.

[jdemeyer]

comment:31

You make some good points which I need to think about...

I never said it was easy, but I like challenges :-)

[roed314]

comment:32

Jeroen, are you planning on working on this soon? If not, I think it's worth trying to get an implementation based on Xavier's prototype into Sage. It has a huge performance impact, and I don't want to see it languish because we move on to other things.

[jdemeyer]

comment:33

Replying to @roed314:

If not, I think it's worth trying to get an implementation based on Xavier's prototype into Sage.

You are basically proposing to have two different semi-working pool implementations (the one from Integer and this one) in Sage?

[roed314]

comment:34

Replying to @jdemeyer:

Replying to @roed314:

If not, I think it's worth trying to get an implementation based on Xavier's prototype into Sage.

You are basically proposing to have two different semi-working pool implementations (the one from Integer and this one) in Sage?

I didn't say this ticket was ready for positive review yet. But what makes these implementations "semi-working?" The integer one has been in Sage for a long time and seems to be useful.

As for having two implementations, I'd be curious to see how the speed of the current integer pool compares with Xavier's implementation. If nothing else, it would give us an idea of how costly performance-wise the decision to use the parent to store the pool is.

[xcaruso]

comment:35

Replying to @roed314:

As for having two implementations, I'd be curious to see how the speed of the current integer pool compares with Xavier's implementation. If nothing else, it would give us an idea of how costly performance-wise the decision to use the parent to store the pool is.

The pool for integers is faster (a simple addition takes ~70ns compared to ~110ns for ZpFM on my laptop). I suppose that the difference is the time needed to look for the address of the pool (it is hardcoded in the new/dealloc functions for the integers).

[jdemeyer]

comment:36

I have an idea for this. Instead of storing the pool in the parent, store the pool as a static C variable inside the Cython module. This is fast, general but ugly. Since one cannot dynamically create functions in C, this would mean that a single Cython module could only use a fixed number of pools.

[jdemeyer]

comment:37

I have (finally) finished my pool implementation in #17670. It is meant to be quite generally applicable.

[roed314]

Changed keywords from pool to pool, padicIMA