Refactor integer vectors using ClonableIntArray Cython data structure

[nborie]

Why that ? Because :

• Integer Vectors have no element class
• Integer Vectors elements must be immutable and hashable
• Clean the old code with new specification
• Add documentation
• Deal with coeherence beetween extra arguments of the constructor
• ...

[tscrim]

Initial version.

[vdelecroix]

Please update the patch as it does not apply on sage-5.10

patching file sage/combinat/integer_vector_weighted.py
Hunk #1 FAILED at 2
Hunk #3 FAILED at 64
Hunk #4 FAILED at 173

[tscrim]

New version (which can be commuted past #14101 and #14772 at minor cost due to doc[string] changes). Also part of #12913.

[tscrim]

Branch version at public/refactor_integer_vectors-12453 but trac is responding with a 'unicode' object not callable error.

[tscrim]

New commits:

​ef2ddce

#12453: Refactored IntegerVectors to use ClonableIntArray.

[git]

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

​eb793cc	Merge branch 'develop' into public/refactor_integer_vectors-12453
​b9f278e	Merge branch 'develop' into public/refactor_integer_vectors-12453

[git]

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

​12bac19

Merge branch 'develop' into public/refactor_integer_vectors-12453

[git]

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

​04c5239	Merge branch 'develop' into public/refactor_integer_vectors-12453
​7393d3a	Merge branch 'develop' into public/refactor_integer_vectors-12453
​3008ee6	Merge branch 'develop' into public/refactor_integer_vectors-12453

[ncohen]

Before this branch

sage: %time _=list(IntegerVectors(5,22))
CPU times: user 1.78 s, sys: 8 ms, total: 1.78 s
Wall time: 1.81 s

After the branch

sage: %time _=list(IntegerVectors(5,22))
CPU times: user 19.3 s, sys: 60 ms, total: 19.4 s
Wall time: 19.6 s

With a 5-lines code

from itertools import combinations
def integervectors(n,k):
    L = n+k-1
    for x in combinations(range(L),k-1):
        l = [x[i] - x[i-1]-1 for i in range(1,k-1)]
        l.insert(0,x[0])
        l.append(L-x[-1]-1)
        yield l

sage: %time _=list(integervectors(5,22))
CPU times: user 492 ms, sys: 16 ms, total: 508 ms
Wall time: 515 ms

I think this can be classified as a severe regression. Besides, it is probably better to avoid this kind of stuff present in your branch:

for c in IntegerVectors(self.size - k, i-1):
    c = list(c)

If you only want the data, don't generate complex objects in the first place.

Nathann

[tscrim]

While this algorithm works (modulo corner cases), it doesn't return them in lex order (which is something we'd want to do). Can you give a variant of it which does yield in lex order?

[tscrim]

Nevermind, I think I have one.

[ncohen]

?

On which instance doesn't it give a lexicographic ordering ? O_o

Nathann

[tscrim]

(1,2) gives: [0, 1] [1, 0]. In fact, try (3,3) and it's not something easily tweaked.

[ncohen]

O_o

sage: list(integervectors(1,2))
[[0, 1], [1, 0]]
sage: list(integervectors(3,3))
[[0, 0, 3],
 [0, 1, 2],
 [0, 2, 1],
 [0, 3, 0],
 [1, 0, 2],
 [1, 1, 1],
 [1, 2, 0],
 [2, 0, 1],
 [2, 1, 0],
 [3, 0, 0]]

Isn't that the lexicographic ordering ? O_o

sage: list(integervectors(3,3)) == sorted(list(integervectors(3,3)))
True

[tscrim]

I meant revlex.

[ncohen]

By your convention, I mean revlex.

Me and quite a lot of people (wikipedia, dictionaries, phone books, Python) seem to agree on what a lexicographic ordering is :-P

It looks like IntegerVector returns them in decreasing lexicographic order, so I guess that's what you call "revlex" (sorry I always mix colex and revlex).

What about computing the complement of x ? In Python it wastes a lot of time, but the algorithm works.... :-P

def integervectors(n,k):
    L = n+k-1
    for x in combinations(range(L),L-(k-1)):
        x_complement = []
        j = 0
        for i in range(L):
            if x[j] == i:
                if j < L-(k-1)-1:
		    j += 1
		continue
            else:
                x_complement.append(i)
	x = x_complement
        l = [x[i] - x[i-1]-1 for i in range(1,k-1)]
        l.insert(0,x[0])
        l.append(L-x[-1]-1)
        yield l

sage: list(integervectors(5,5)) == [list(map(int,x)) for x in IntegerVectors(5,5)]
True

[git]

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

​5a88839	Merge branch 'public/refactor_integer_vectors-12453' of trac.sagemath.org:sage into public/refactor_integer_vectors-12453
​ae5db31	Merge branch 'develop' into public/refactor_integer_vectors-12453
​71858e1	Fixes for integer vectors.

[tscrim]

I thought I had a method but it didn't work. Python's itertool forces it through lex ordering, so I just did a brute compute and reverse (which is far less than ideal). I'll look into your revised algorithm tonight.

[git]

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

​5f18c77	Merge branch 'develop' into public/refactor_integer_vectors-12453
​d904ede	Merge branch 'develop' into public/refactor_integer_vectors-12453
​0fb27ab	Merge branch 'develop' into public/refactor_integer_vectors-12453
​31402be	Merge branch 'develop' into public/refactor_integer_vectors-12453
​0addeb2	Merge branch 'public/refactor_integer_vectors-12453' of trac.sagemath.org:sage into public/refactor_integer_vectors-12453

[git]

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

​1501865	Merge commit '71858e198f18832b07176233438914f7d90bd35f' into public/refactor_integer_vectors-12453
​822e1cb	Merge branch 'public/refactor_integer_vectors-12453' of trac.sagemath.org:sage into public/refactor_integer_vectors-12453

[tscrim]

Hey Nathann,

I've implemented your algorithm and everything seems to work. Can you do the rest of the review for this?

[ncohen]

Hello !

I've implemented your algorithm and everything seems to work. Can you do the rest of the review for this?

No, sorry. Your branch contains 14 commits, almost all of which are entitled "Merge with develop". Besides, I see some code in your branch in which you just change the indentation, and so it seems that I should not re-review all that code, but given how your branch is made I have no way to know what needs an actual review.

Besides, I can spend time on the review of any "local" thing (like this enumeration algorithm) and I will do it gladly if you have anything specific in mind, but I hate parents, elements and almost anything that is immutable. I am the last person you want to review code like that.

I would start to make unpleasant reviews like: "It has been reported on Sage-devel that having a cached function return a UniqueRepresentation object resulted in a memory leak. Clearly those integer vectors will be used by cached function, so you are creating a new memory leak until this finally gets fixed".

​https://groups.google.com/d/topic/sage-devel/q5uy_lI11jg/discussion

So I'm sorry but you probably want somebody else to review this ticket.

Nathann

[chapoton]

needs rebase, des not apply

[git]

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

​8bc466d

Merge branch 'public/refactor_integer_vectors-12453' of git://trac.sagemath.org/sage into public/refactor_integer_vectors-12453

[chapoton]

doc does not build:

+[dochtml] OSError: [combinat ] /home/worker/sage-patchbot/local/lib/python2.7/site-packages/sage/combinat/integer_vector.py:docstring of sage.combinat.integer_vector.IntegerVectors_nnondescents:9: WARNING: Inline literal start-string without end-string.

and one should no longer use it.next() bu instead use next(it)

++ sage: [it.next() for x in range(10)] ++ sage: [it.next() for x in range(10)] ++ sage: [it.next() for x in range(10)]

[git]

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

​8a32e27	Merge branch 'develop' into public/refactor_integer_vectors-12453
​1762096	Fixing docbuilding (hopefully) and Python3 compatibility.

[tscrim]

This should fix the doc (although I can't test right now because Sage is recompiling) and fixed the next.

[tscrim]

Followup, doc built cleanly for me.

[chapoton]

triggers doctest failures in sandpiles

[git]

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

​bab162b

Fixing doctest failures in sandpile.py.

[tscrim]

Fixed.

[tscrim]

Patchbot is green.

[chapoton]

Before

sage: %timeit list(IntegerVectors(5,22))
1 loop, best of 3: 190 ms per loop

After

sage: %timeit list(IntegerVectors(5,22)) 
1 loop, best of 3: 3.86 s per loop

which looks really bad..

[tscrim]

Basically all of the time is eaten up by integer_vectors_nk_fast_iter. I was hoping to line profile it, but that is broken since the IPython upgrade. I'm looking into this.

[tscrim]

So it seems Nathann's algorithm is just slower than the original version, so I'm just reverting it. I would like to %lprun it... *sigh*

[git]

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

​c8d2f6c

Reverting to previous iterator.

[git]

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

​d312832

Take advantage of the list-returning iterator.

[tscrim]

Now I get about a 3x slowdown for the iterator over the parent, but considering that this is basically overhead from the parent/element stuff, we won't be able to get much else. Plus we are at such small time scales and if you're iterating over the parent, then this should not be the bottleneck.

However, calling the iterator itself is now about 10% faster than before. So I also update those parts of the codebase which want a honest list back and had them call the iterator directly.

[git]

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

​60070a9	Merge branch 'develop' into public/refactor_integer_vectors-12453
​92360bd	Fixing doctests from experiments.

[git]

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

​a4be991

Merge branch 'develop' into public/refactor_integer_vectors-12453

[tscrim]

Patchbot is green.

[git]

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

​a52b821

Merge branch 'develop' into public/refactor_integer_vectors-12453

[git]

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

​f4f8149

Merge branch 'develop' into public/refactor_integer_vectors-12453

[tscrim]

Rebased on 7.4.beta6.

[git]

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

​282f39b

We have stricter equality checks based upon the parent.

[git]

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

​074dc19	Merge branch 'develop' into public/refactor_integer_vectors-12453
​7401293	Merge branch 'develop' into public/refactor_integer_vectors-12453
​c6dd087	Merge branch 'develop' into public/refactor_integer_vectors-12453
​98ecbad	Merge branch 'develop' into public/refactor_integer_vectors-12453
​ddce440	Merge branch 'develop' into public/refactor_integer_vectors-12453
​ff49fdf	Merge branch 'develop' into public/refactor_integer_vectors-12453

[chapoton]

does not apply

[git]

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

​0feb74d	Merge branch 'develop' into public/refactor_integer_vectors-12453
​707b519	Merge branch 'develop' into public/refactor_integer_vectors-12453

[tscrim]

I would appreciate it if you could finish the review Frédéric.

[git]

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

​2c221cf

Fixing trivial doctest.

[chapoton]

typo "yeilds Python"

I am not sure I am able to do a review. This is rather large a ticket..

Would you please provide some timings ? I am still a lot worried about that.

And explain again what is gained, maybe at the loss of some speed ?

[chapoton]

before

sage: %timeit list(IntegerVectors(5,22))
1 loop, best of 3: 193 ms per loop

after

sage: %timeit list(IntegerVectors(5,22)) 
1 loop, best of 3: 622 ms per loop

so this is not so bad, but still a 3 times slowdown. What do we gain for this prize ?

[git]

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

​0b75147

Fixing typo yeilds -> yields.

[tscrim]

That is around what I am getting as well. The advantage is that this is now a proper parent class with elements and fits into the rest of Sage. If you want to have the speed but not the parent/element overhead, I provided an iterator for that:

sage: %timeit list(IntegerVectors(5,22))
1 loop, best of 3: 238 ms per loop
sage: from sage.combinat.integer_vector import integer_vectors_nk_fast_iter
sage: %timeit list(integer_vectors_nk_fast_iter(5,22))
10 loops, best of 3: 63.7 ms per loop

Old:

sage: %timeit list(IntegerVectors(5,22))
10 loops, best of 3: 76.4 ms per loop

Although if you use int and Cython, you can get a very fast iterator. Although converting those back to Integer's was actually slower than working directly with Integer's.

I now see the problem with why that was taking so long. The class I'm using actually stores the input data as int's, not Integer's. So I think I need to change the base class for the elements.

[git]

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

​fa63e8f

Using ClonableArray instead of ClonableIntArray.

[tscrim]

Okay, using ClonableArray makes things a little bit better:

%timeit list(IntegerVectors(5,22))
1 loop, best of 3: 209 ms per loop

[git]

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

​5553a1b

Squeezing some more speed out of the iterator.

[git]

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

​c37d077

Make sure every element in the list is a Sage Integer.

[tscrim]

By not popping and pushing the list (the iterator wants a fixed length) and some reworking, I got it to:

sage: %timeit list(IntegerVectors(5,22))
1 loop, best of 3: 188 ms per loop

Although I did get some slowdown because rem was not an Integer for the entire loop. So I think this is probably as fast as I can get it.

[git]

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

​4aaba42

trac 12453 reviewer's commit

[chapoton]

Looks better now indeed. I have made a reviewer's commit (cosmetic).

Once the bot is green, you can set a positive review.

[tscrim]

Bot is essentially green, so positive review. Thank you.

[vbraun]

FYI I'm only merging tickets whose dependencies are merged git branches.