Usainboltz package: fast Boltzmann random generation of tree-like structures

[Kerl13]

Usain Boltz is a !Python/Cython/C++ library that automates the random generation of tree-like structures.
It allows to describe a combinatorial structure using a specification in the style of “Analytic Combinatorics” and, using the Boltzmann sampling framework, it produces a fast, uniform, and approximate size sampler of objects described by this specification.

https://gitlab.com/ParComb/usain-boltz

Depends on #34251

CC: @sagetrac-tmonteil @MatthieuDien @Kerl13 @mantepse

Component: packages: optional

Author: Martin Pépin, Matthieu Dien

Branch/Commit: u/MartinPepin/usainboltz @ d8e42b9

Reviewer: Thierry Monteil

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

[Kerl13]

Branch: u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

[sagetrac-git]

Commit: 693df81

[sagetrac-git]

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

693df81

Boltzmann sampling: module-wide documentation

[sagetrac-git]

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

75ec37c

Use sage's randstate API for random number generation

[sagetrac-git]

Changed commit from 693df81 to 75ec37c

[sagetrac-git]

Changed commit from 75ec37c to 8b40cc1

[sagetrac-git]

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

8b40cc1

Boltzmann: document the generator module

[sagetrac-git]

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

b798133	Boltzmann(Grammar): `labelled` optional argument
1c7b6b0	Integrate Boltzmann's doc into the reference manual

[sagetrac-git]

Changed commit from 8b40cc1 to 1c7b6b0

[MatthieuDien]

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

[Kerl13]

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

[MatthieuDien]

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

[Kerl13]

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

[sagetrac-git]

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

1da6bd2

Boltzmann(Oracle): pep8 + fix doctests

[sagetrac-git]

Changed commit from 1c7b6b0 to 1da6bd2

[sagetrac-git]

Changed commit from 1da6bd2 to 5303f2a

[sagetrac-git]

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

5303f2a

Boltzmann: fix import statements in doctests

[MatthieuDien]

Changed author from Martin Pépin to Martin Pépin, Matthieu Dien

[MatthieuDien]

New commits:

5303f2a

Boltzmann: fix import statements in doctests

[sagetrac-git]

Changed commit from 5303f2a to 04ca7e6

[sagetrac-git]

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

b648771	Fix various generator bugs
04ca7e6	Boltzmann(Generator): towards labellings

[sagetrac-git]

Changed commit from 04ca7e6 to a25d00c

[sagetrac-git]

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

71271d4	Boltzmann: first implementation of labellings
a25d00c	Boltzmann: clean the generator, labelling works

[sagetrac-git]

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

b94b94a	Boltzmann: default builders show the labels
70e9b92	Boltzmann: shuffle the labels of an atom of size >1

[Kerl13]

comment:43

Ok now it works! Sorry for the noise, there had been a problem at make configure that I didn't spot when I built sage

[mkoeppe]

comment:45

+++ b/build/pkgs/usainboltz/dependencies
@@ -0,0 +1,4 @@
+$(PYTHON) cython | $(PYTHON_TOOLCHAIN)

It's better to put cython after the |, to make it an order-only dependency

[mkoeppe]

comment:46

On macOS (with clang)

[usainboltz]       gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -iwithsysroot/System/Library/Frameworks/System.framework/PrivateHeaders -iwithsysroot/Applications/Xcode.app/Contents/Developer/Library/Frameworks/Python3.framework/Versions/3.8/Headers -Werror=implicit-function-declaration -Isrc/xoshiro -Isrc/usainboltz -I/Users/mkoeppe/s/sage/sage-rebasing/worktree-gcc11/local/var/lib/sage/venv-python3.8/include -I/Applications/Xcode.app/Contents/Developer/Library/Frameworks/Python3.framework/Versions/3.8/Headers -c src/usainboltz/cpp_simulator.cpp -o build/temp.macosx-10.14-x86_64-cpython-38/src/usainboltz/cpp_simulator.o
[usainboltz]       In file included from src/usainboltz/cpp_simulator.cpp:7:
[usainboltz]       src/usainboltz/cpp_simulator.hpp:45:7: error: union member '_as_product' has a non-trivial copy constructor
[usainboltz]           } _as_product;
[usainboltz]             ^
[usainboltz]       src/usainboltz/cpp_simulator.hpp:44:28: note: because field of type 'std::vector<CRule *>' has a user-provided copy constructor
[usainboltz]             std::vector<CRule *> args;
[usainboltz]                                  ^
[usainboltz]       /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/vector:581:5: note: declared here
[usainboltz]           vector(const vector& __x);
[usainboltz]           ^
[usainboltz]       In file included from src/usainboltz/cpp_simulator.cpp:7:
[usainboltz]       src/usainboltz/cpp_simulator.hpp:50:37: error: a space is required between consecutive right angle brackets (use '> >')
[usainboltz]             std::vector<std::vector<double>> weights;
[usainboltz]                                           ^~
[usainboltz]                                           > >

[mkoeppe]

comment:47

I see that cvxpy is a dependency of this package. You may be interested in #34251, which adds it as an SPKG

[sagetrac-git]

Changed commit from 5f09d11 to b00b065

[sagetrac-git]

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

b00b065

usainboltz: make cython an order-only dependency

[Kerl13]

comment:49

It's better to put cython after the |, to make it an order-only dependency

Good point, sorry I missed that

[Kerl13]

comment:50

Replying to Matthias Köppe:

On macOS (with clang)

[usainboltz]       src/usainboltz/cpp_simulator.hpp:50:37: error: a space is required between consecutive right angle brackets (use '> >')
[usainboltz]             std::vector<std::vector<double>> weights;
[usainboltz]                                           ^~

I was not aware of that issue, thanks for reporting, I'll add clang to usainboltz' CI

[mkoeppe]

comment:51

Probably needs -std=c++11 or something like this

[Kerl13]

comment:52

Replying to Matthias Köppe:

I see that cvxpy is a dependency of this package. You may be interested in #34251, which adds it as an SPKG

Yes it is indeed interesting. How do I benefit from this?
Will sage's pip use the optional cvxpy package if I add it as a dependency? Or do I need to switch to the normal package format for usainboltz`? I'll be happy to do so if it's considered better.

Btw, Thierry told me a few days ago that our (only “real” dependency paganini might be of interest for sage as well. Another good reason to package everything as normal?

[Kerl13]

comment:53

Replying to Matthias Köppe:

Probably needs -std=c++11 or something like this

I'll check that but I think I prefer to follow the error message's suggestion if it makes the library compatible with more compilers / compiler versions

[mkoeppe]

comment:54

See #32074 for detailed info on compiler supported by Sage & related software

[Kerl13]

comment:55

Replying to Matthias Köppe:

I fixed the compilation issue with clang (at list on my setup).

Would you mind checking whether sage -pip install git+https://gitlab.com/ParComb/usain-boltz#master works for you before I release a new version? That would be really nice.

A few warnings are to be expected because cython does not produce fully c++11 compatible code (cython/cython#4687). I don't know to what extent this is a problem.

On macOS (with clang)

[usainboltz]       gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -iwithsysroot/System/Library/Frameworks/System.framework/PrivateHeaders -iwithsysroot/Applications/Xcode.app/Contents/Developer/Library/Frameworks/Python3.framework/Versions/3.8/Headers -Werror=implicit-function-declaration -Isrc/xoshiro -Isrc/usainboltz -I/Users/mkoeppe/s/sage/sage-rebasing/worktree-gcc11/local/var/lib/sage/venv-python3.8/include -I/Applications/Xcode.app/Contents/Developer/Library/Frameworks/Python3.framework/Versions/3.8/Headers -c src/usainboltz/cpp_simulator.cpp -o build/temp.macosx-10.14-x86_64-cpython-38/src/usainboltz/cpp_simulator.o
[...]

By the way, I just noticed you seemed to use gcc from the log you pasted.
Is this a mistake or is gcc an alias for clang in your setup?

[sagetrac-git]

Changed commit from b00b065 to 76e06f0

[sagetrac-git]

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

8392936	Add the optas optional package
2397f14	Add the paganini optional package
76e06f0	Turn usainboltz into a normal package

[Kerl13]

Dependencies: #34251

[sagetrac-git]

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

d8e42b9

Bump usainboltz to 0.2.1

[sagetrac-git]

Changed commit from 76e06f0 to d8e42b9

[Kerl13]

comment:59

I could finally get my hands on a mac this afternoon so I could test the compilation there and release a new version, sorry for the noise

[mkoeppe]

comment:60

Replying to Martin Pépin:

By the way, I just noticed you seemed to use gcc from the log you pasted.
Is this a mistake or is gcc an alias for clang in your setup?

On macOS, the gcc binary provided by Xcode is a compatibility shim around Apple's version of clang.

[mkoeppe]

comment:61

Replying to Martin Pépin:

Replying to Matthias Köppe:

I see that cvxpy is a dependency of this package. You may be interested in #34251, which adds it as an SPKG

Yes it is indeed interesting. How do I benefit from this?

#34251 is waiting for reviewers...

Will sage's pip use the optional cvxpy package if I add it as a dependency? Or do I need to switch to the normal package format for usainboltz`? I'll be happy to do so if it's considered better.

When #34251 is merged, we should add cvxpy to build/pkgs/usainboltz/dependencies.
This will avoid the conflict (possible races in parallel builds) between installing cvxpy from our package and getting cvxpy.

There's no need to switch usainboltz to normal.

[mkoeppe]

comment:62

Replying to Martin Pépin:

Btw, Thierry told me a few days ago that our (only “real” dependency paganini might be of interest for sage as well.

I can't comment on this; it's outside of my domain of mathematical expertise.

Another good reason to package everything as normal?

No, I'd say it's best to set things up as pip packages as you did. The additional maintenance burden (upgrade tickets) with normal packages is typically only warranted if we have tight integration of the provided functionality in Sage.

[mkoeppe]

comment:63

Oh, now I see you have made the switch to normal packages already on the new branch.
Then it's best to merge the branch of #34251 here. The current branch can't be tested because cvxpy is not a package

[mkoeppe]

comment:64

diff --git a/build/pkgs/optas/dependencies b/build/pkgs/optas/dependencies
new file mode 100644
index 00000000..7d1ace1
--- /dev/null
+++ b/build/pkgs/optas/dependencies
@@ -0,0 +1,4 @@
+$(PYTHON) | $(PYTHON_TOOLCHAIN) gcc

There's no need for the gcc here. This dependency is implicit for all packages.

[mkoeppe]

comment:65

Other than that, it's looking good

[Kerl13]

comment:66

Replying to Matthias Köppe:

#34251 is waiting for reviewers...

I think I can do that!