diff options
author | Vincent Ambo <mail@tazj.in> | 2020-07-15T07·20+0100 |
---|---|---|
committer | Vincent Ambo <mail@tazj.in> | 2020-07-15T07·20+0100 |
commit | 7f19d641647ac4ef313ed88d6b5c140983ce5436 (patch) | |
tree | 31b66c81465293da5c093c5dde3e419758c0d6cc /extra/python |
Squashed 'third_party/immer/' content from commit ad3e3556d
git-subtree-dir: third_party/immer git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e
Diffstat (limited to 'extra/python')
-rw-r--r-- | extra/python/CMakeLists.txt | 46 | ||||
-rw-r--r-- | extra/python/README.rst | 42 | ||||
-rw-r--r-- | extra/python/benchmark/test_benchmarks.py | 45 | ||||
-rwxr-xr-x | extra/python/example.py | 21 | ||||
-rw-r--r-- | extra/python/immer/__init__.py | 2 | ||||
m--------- | extra/python/lib/pybind11 | 0 | ||||
-rw-r--r-- | extra/python/src/immer-boost.cpp | 80 | ||||
-rw-r--r-- | extra/python/src/immer-pybind.cpp | 77 | ||||
-rw-r--r-- | extra/python/src/immer-raw.cpp | 402 |
9 files changed, 715 insertions, 0 deletions
diff --git a/extra/python/CMakeLists.txt b/extra/python/CMakeLists.txt new file mode 100644 index 000000000000..11d5fff209ad --- /dev/null +++ b/extra/python/CMakeLists.txt @@ -0,0 +1,46 @@ + +option(USE_PYBIND "bind with pybind1" off) +option(USE_BOOST_PYTHON "bind with boost::python" off) + +if (USE_PYBIND) + set(PYBIND11_CPP_STANDARD -std=c++14) + find_package(Boost 1.56 REQUIRED) + add_subdirectory(lib/pybind11) + pybind11_add_module(immer_python_module src/immer-pybind.cpp) + target_link_libraries(immer_python_module PUBLIC + immer) + +elseif(USE_BOOST_PYTHON) + find_package(PythonInterp) + find_package(PythonLibs) + find_package(Boost 1.56 COMPONENTS python) + python_add_module(immer_python_module src/immer-boost.cpp) + include_directories(immer_python_module PUBLIC + ${immer_include_dir} + ${Boost_INCLUDE_DIRS} + ${PYTHON_INCLUDE_DIRS}) + target_link_libraries(immer_python_module PUBLIC + immer + ${Boost_LIBRARIES} + ${PYTHON_LIBRARIES}) + +else() + find_package(PythonInterp) + find_package(PythonLibs) + + if (NOT PYTHONLIBS_FOUND) + message(STATUS "Disabling Python modules") + return() + endif() + + python_add_module(immer_python_module EXCLUDE_FROM_ALL + src/immer-raw.cpp) + target_include_directories(immer_python_module PUBLIC + ${PYTHON_INCLUDE_DIRS}) + target_link_libraries(immer_python_module PUBLIC + immer + ${PYTHON_LIBRARIES}) + +endif() + +add_custom_target(python DEPENDS immer_python_module) diff --git a/extra/python/README.rst b/extra/python/README.rst new file mode 100644 index 000000000000..7447e99e6281 --- /dev/null +++ b/extra/python/README.rst @@ -0,0 +1,42 @@ + +Python bindings +=============== + +This library includes experimental bindings bring efficient immutable +vectors for the Python language. They were developed as part of the +research for the `ICFP'17 paper`_. The interface is quite +**incomplete**, yet you can already do some things like: + +.. literalinclude:: ../extra/python/example.py + :language: python + :start-after: intro/start + :end-before: intro/end +.. + + **Do you want to help** making these bindings complete and production + ready? Drop a line at `immer@sinusoid.al + <mailto:immer@sinusoid.al>`_ or `open an issue on Github + <https://github.com/arximboldi/immer>`_ + +Installation +------------ +:: + + pip install --user git+https://github.com/arximboldi/immer.git + +Benchmarks +---------- + +The library includes a set of benchmarks that compare it to +`pyrsistent <https://github.com/tobgu/pyrsistent>`_. You can see the +results in the `ICFP'17 paper`_. If you want to run them yourself, +you need to install some dependencies:: + + pip install --user pytest-benchmark pyrsistent + +Then you need to clone the `project repository +<https://github.com/arximboldi/immer>`_ and from its root, run:: + + pytest extra/python/benchmark + +.. _ICFP'17 paper: https://public.sinusoid.es/misc/immer/immer-icfp17.pdf diff --git a/extra/python/benchmark/test_benchmarks.py b/extra/python/benchmark/test_benchmarks.py new file mode 100644 index 000000000000..11e4817c3256 --- /dev/null +++ b/extra/python/benchmark/test_benchmarks.py @@ -0,0 +1,45 @@ + +# immer: immutable data structures for C++ +# Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +# +# This software is distributed under the Boost Software License, Version 1.0. +# See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt + +## + +import immer +import pyrsistent + +BENCHMARK_SIZE = 1000 + +def push(v, n=BENCHMARK_SIZE): + for x in xrange(n): + v = v.append(x) + return v + +def assoc(v): + for i in xrange(len(v)): + v = v.set(i, i+1) + return v + +def index(v): + for i in xrange(len(v)): + v[i] + +def test_push_immer(benchmark): + benchmark(push, immer.Vector()) + +def test_push_pyrsistent(benchmark): + benchmark(push, pyrsistent.pvector()) + +def test_assoc_immer(benchmark): + benchmark(assoc, push(immer.Vector())) + +def test_assoc_pyrsistent(benchmark): + benchmark(assoc, push(pyrsistent.pvector())) + +def test_index_immer(benchmark): + benchmark(index, push(immer.Vector())) + +def test_index_pyrsistent(benchmark): + benchmark(index, push(pyrsistent.pvector())) diff --git a/extra/python/example.py b/extra/python/example.py new file mode 100755 index 000000000000..36f7333c4f0f --- /dev/null +++ b/extra/python/example.py @@ -0,0 +1,21 @@ +#!/usr/bin/env python## + +# immer: immutable data structures for C++ +# Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +# +# This software is distributed under the Boost Software License, Version 1.0. +# See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt + + +# include:intro/start +import immer + +v0 = immer.Vector().append(13).append(42) +assert v0[0] == 13 +assert v0[1] == 42 +assert len(v0) == 2 + +v1 = v0.set(0, 12) +assert v0.tolist() == [13, 42] +assert v1.tolist() == [12, 42] +# include:intro/end diff --git a/extra/python/immer/__init__.py b/extra/python/immer/__init__.py new file mode 100644 index 000000000000..e4702b40e4a1 --- /dev/null +++ b/extra/python/immer/__init__.py @@ -0,0 +1,2 @@ + +from immer_python_module import * diff --git a/extra/python/lib/pybind11 b/extra/python/lib/pybind11 new file mode 160000 +Subproject 1eaacd19f6de9a053570c21de6d173efc2304bc diff --git a/extra/python/src/immer-boost.cpp b/extra/python/src/immer-boost.cpp new file mode 100644 index 000000000000..0ea42354b6b1 --- /dev/null +++ b/extra/python/src/immer-boost.cpp @@ -0,0 +1,80 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <boost/python.hpp> +#include <boost/python/suite/indexing/vector_indexing_suite.hpp> + +#include <immer/vector.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +namespace { + +struct heap_t +{ + template <typename ...Tags> + static void* allocate(std::size_t size, Tags...) + { + return PyMem_Malloc(size); + } + + template <typename ...Tags> + static void deallocate(std::size_t, void* obj, Tags...) + { + PyMem_Free(obj); + } +}; + +using memory_t = immer::memory_policy< + immer::unsafe_free_list_heap_policy<heap_t>, + immer::unsafe_refcount_policy>; + +template <typename Vector> +struct immer_vector_indexing_suite : boost::python::vector_indexing_suite< + Vector, true, immer_vector_indexing_suite<Vector>> +{ + using value_t = typename Vector::value_type; + using index_t = typename Vector::size_type; + using object_t = boost::python::object; + + static void forbidden() { throw std::runtime_error{"immutable!"}; } + static void todo() { throw std::runtime_error{"TODO!"}; } + + static const value_t& get_item(const Vector& v, index_t i) { return v[i]; } + static object_t get_slice(const Vector&, index_t, index_t) { todo(); } + + static void set_item(const Vector&, index_t, const value_t&) { forbidden(); } + static void delete_item(const Vector&, index_t) { forbidden(); } + static void set_slice(const Vector&, index_t, index_t, const value_t&) { forbidden(); } + static void delete_slice(const Vector&, index_t, index_t) { forbidden(); } + template <typename Iter> + static void set_slice(const Vector&, index_t, index_t, Iter, Iter) { forbidden(); } + template <class Iter> + static void extend(const Vector& container, Iter, Iter) { forbidden(); } +}; + +} // anonymous namespace + + +BOOST_PYTHON_MODULE(immer_python_module) +{ + using namespace boost::python; + + using vector_t = immer::vector<object, memory_t>; + + class_<vector_t>("Vector") + .def(immer_vector_indexing_suite<vector_t>()) + .def("append", + +[] (const vector_t& v, object x) { + return v.push_back(std::move(x)); + }) + .def("set", + +[] (const vector_t& v, std::size_t i, object x) { + return v.set(i, std::move(x)); + }) + ; +} diff --git a/extra/python/src/immer-pybind.cpp b/extra/python/src/immer-pybind.cpp new file mode 100644 index 000000000000..8f8aab1231f8 --- /dev/null +++ b/extra/python/src/immer-pybind.cpp @@ -0,0 +1,77 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <pybind11/pybind11.h> + +#include <immer/vector.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +namespace { + +struct heap_t +{ + template <typename ...Tags> + static void* allocate(std::size_t size, Tags...) + { + return PyMem_Malloc(size); + } + + template <typename ...Tags> + static void deallocate(std::size_t, void* obj, Tags...) + { + PyMem_Free(obj); + } +}; + +using memory_t = immer::memory_policy< + immer::unsafe_free_list_heap_policy<heap_t>, + immer::unsafe_refcount_policy>; + +} // anonymous namespace + +namespace py = pybind11; + +PYBIND11_PLUGIN(immer_python_module) +{ + py::module m("immer", R"pbdoc( + Immer + ----- + .. currentmodule:: immer + .. autosummary:: + :toctree: _generate + Vector + )pbdoc"); + + using vector_t = immer::vector<py::object, memory_t>; + + py::class_<vector_t>(m, "Vector") + .def(py::init<>()) + .def("__len__", &vector_t::size) + .def("__getitem__", + [] (const vector_t& v, std::size_t i) { + if (i > v.size()) + throw py::index_error{"Index out of range"}; + return v[i]; + }) + .def("append", + [] (const vector_t& v, py::object x) { + return v.push_back(std::move(x)); + }) + .def("set", + [] (const vector_t& v, std::size_t i, py::object x) { + return v.set(i, std::move(x)); + }); + +#ifdef VERSION_INFO + m.attr("__version__") = py::str(VERSION_INFO); +#else + m.attr("__version__") = py::str("dev"); +#endif + + return m.ptr(); +} diff --git a/extra/python/src/immer-raw.cpp b/extra/python/src/immer-raw.cpp new file mode 100644 index 000000000000..283f973c8d0f --- /dev/null +++ b/extra/python/src/immer-raw.cpp @@ -0,0 +1,402 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +extern "C" { +#include <Python.h> +#include <structmember.h> +} + +#include <immer/vector.hpp> +#include <immer/algorithm.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#include <iostream> + +namespace { + +struct heap_t +{ + template <typename ...Tags> + static void* allocate(std::size_t size, Tags...) + { + return PyMem_Malloc(size); + } + + template <typename ...Tags> + static void deallocate(std::size_t, void* obj, Tags...) + { + PyMem_Free(obj); + } +}; + +struct object_t +{ + struct wrap_t {}; + struct adopt_t {}; + + PyObject* ptr_ = nullptr; + + object_t() = delete; + ~object_t() { Py_XDECREF(ptr_); } + + explicit object_t(PyObject* p, wrap_t) : ptr_{p} {} + explicit object_t(PyObject* p, adopt_t) : ptr_{p} + { + assert(p); + Py_INCREF(p); + } + + static object_t wrap(PyObject* p) { return object_t{p, wrap_t{}}; } + static object_t adopt(PyObject* p) { return object_t{p, adopt_t{}}; } + + object_t(const object_t& o) : ptr_(o.ptr_) { Py_INCREF(ptr_); } + object_t(object_t&& o) { std::swap(ptr_, o.ptr_); } + + object_t& operator=(const object_t& o) + { + Py_XINCREF(o.ptr_); + Py_XDECREF(ptr_); + ptr_ = o.ptr_; + return *this; + } + object_t& operator=(object_t&& o) + { + std::swap(ptr_, o.ptr_); + return *this; + } + + PyObject* release() + { + auto p = ptr_; + ptr_ = nullptr; + return p; + } + + PyObject* get() const { return ptr_; } +}; + +using memory_t = immer::memory_policy< + immer::unsafe_free_list_heap_policy<heap_t>, + immer::unsafe_refcount_policy>; + +using vector_impl_t = immer::vector<object_t, memory_t>; + +struct vector_t +{ + PyObject_HEAD + vector_impl_t impl; + PyObject* in_weakreflist; + + static PyTypeObject type; +}; + +vector_t* empty_vector = nullptr; + +vector_t* make_vector() +{ + auto* v = PyObject_GC_New(vector_t, &vector_t::type); + new (&v->impl) vector_impl_t{}; + v->in_weakreflist = nullptr; + PyObject_GC_Track((PyObject*)v); + return v; +} + +vector_t* make_vector(vector_impl_t&& impl) +{ + auto v = PyObject_GC_New(vector_t, &vector_t::type); + new (&v->impl) vector_impl_t{std::move(impl)}; + v->in_weakreflist = nullptr; + PyObject_GC_Track((PyObject*)v); + return v; +} + +auto todo() +{ + PyErr_SetString(PyExc_RuntimeError, "immer: todo!"); + return nullptr; +} + +void vector_dealloc(vector_t* self) +{ + if (self->in_weakreflist != nullptr) + PyObject_ClearWeakRefs((PyObject*)self); + + PyObject_GC_UnTrack((PyObject*)self); + Py_TRASHCAN_SAFE_BEGIN(self); + + self->impl.~vector_impl_t(); + + PyObject_GC_Del(self); + Py_TRASHCAN_SAFE_END(self); +} + +PyObject* vector_to_list(vector_t* self) +{ + auto list = PyList_New(self->impl.size()); + auto idx = 0; + immer::for_each(self->impl, [&] (auto&& obj) { + auto o = obj.get(); + Py_INCREF(o); + PyList_SET_ITEM(list, idx, o); + ++idx; + }); + return list; +} + +PyObject* vector_repr(vector_t *self) +{ + auto list = vector_to_list(self); + auto list_repr = PyObject_Repr(list); + Py_DECREF(list); + + if (!list_repr) return nullptr; + +#if PY_MAJOR_VERSION >= 3 + auto s = PyUnicode_FromFormat("%s%U%s", "immer.vector(", list_repr, ")"); + Py_DECREF(list_repr); +#else + auto s = PyString_FromString("immer.vector("); + PyString_ConcatAndDel(&s, list_repr); + PyString_ConcatAndDel(&s, PyString_FromString(")")); +#endif + return s; +} + +Py_ssize_t vector_len(vector_t* self) +{ + return self->impl.size(); +} + +PyObject* vector_extend(vector_t* self, PyObject* iterable) +{ + return todo(); +} + +vector_t* vector_append(vector_t* self, PyObject *obj) +{ + assert(obj != nullptr); + return make_vector(self->impl.push_back(object_t::adopt(obj))); +} + +vector_t* vector_set(vector_t* self, PyObject* args) +{ + PyObject* obj = nullptr; + Py_ssize_t pos; + // the n parses for size, the O parses for a Python object + if(!PyArg_ParseTuple(args, "nO", &pos, &obj)) { + return nullptr; + } + if (pos < 0) + pos += self->impl.size(); + if (pos < 0 || pos > (Py_ssize_t)self->impl.size()) { + PyErr_Format(PyExc_IndexError, "Index out of range: %zi", pos); + return nullptr; + } + return make_vector(self->impl.set(pos, object_t::adopt(obj))); +} + +PyObject* vector_new(PyTypeObject* subtype, PyObject *args, PyObject *kwds) +{ + Py_INCREF(empty_vector); + return (PyObject*)empty_vector; +} + +long vector_hash(vector_t* self) +{ + todo(); + return 0; +} + +PyObject* vector_get_item(vector_t* self, Py_ssize_t pos) +{ + if (pos < 0) + pos += self->impl.size(); + if (pos < 0 || pos >= (Py_ssize_t)self->impl.size()) { + PyErr_Format(PyExc_IndexError, "Index out of range: %zi", pos); + return nullptr; + } + auto r = self->impl[pos]; + return r.release(); +} + +PyObject* vector_subscript(vector_t* self, PyObject* item) +{ + if (PyIndex_Check(item)) { + auto i = PyNumber_AsSsize_t(item, PyExc_IndexError); + if (i == -1 && PyErr_Occurred()) + return nullptr; + return vector_get_item(self, i); + } else if (PySlice_Check(item)) { + return todo(); + } else { + PyErr_Format(PyExc_TypeError, + "vector indices must be integers, not %.200s", + Py_TYPE(item)->tp_name); + return nullptr; + } +} + +PyObject* vector_repeat(vector_t* self, Py_ssize_t n) +{ + return todo(); +} + +int vector_traverse(vector_t* self, visitproc visit, void* arg) +{ + auto result = 0; + immer::all_of(self->impl, [&] (auto&& o) { + return 0 == (result = [&] { + Py_VISIT(o.get()); + return 0; + }()); + }); + return result; +} + +PyObject* vector_richcompare(PyObject* v, PyObject* w, int op) +{ + return todo(); +} + +PyObject* vector_iter(PyObject* self) +{ + return todo(); +} + +PyMethodDef vector_methods[] = +{ + {"append", (PyCFunction)vector_append, METH_O, "Appends an element"}, + {"set", (PyCFunction)vector_set, METH_VARARGS, "Inserts an element at the specified position"}, + {"extend", (PyCFunction)vector_extend, METH_O|METH_COEXIST, "Extend"}, + {"tolist", (PyCFunction)vector_to_list, METH_NOARGS, "Convert to list"}, + {0} +}; + +PyMemberDef vector_members[] = +{ + {0} /* sentinel */ +}; + +PySequenceMethods vector_sequence_methods = +{ + (lenfunc)vector_len, /* sq_length */ + (binaryfunc)vector_extend, /* sq_concat */ + (ssizeargfunc)vector_repeat, /* sq_repeat */ + (ssizeargfunc)vector_get_item, /* sq_item */ + 0, /* sq_slice */ + 0, /* sq_ass_item */ + 0, /* sq_ass_slice */ + 0, /* sq_contains */ + 0, /* sq_inplace_concat */ + 0, /* sq_inplace_repeat */ +}; + +PyMappingMethods vector_mapping_methods = +{ + (lenfunc)vector_len, + (binaryfunc)vector_subscript, + 0 +}; + +PyTypeObject vector_t::type = +{ + PyVarObject_HEAD_INIT(NULL, 0) + "immer.Vector", /* tp_name */ + sizeof(vector_t), /* tp_basicsize */ + 0, /* tp_itemsize */ + (destructor)vector_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + (reprfunc)vector_repr, /* tp_repr */ + 0, /* tp_as_number */ + &vector_sequence_methods, /* tp_as_sequence */ + &vector_mapping_methods, /* tp_as_mapping */ + (hashfunc)vector_hash, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ + "", /* tp_doc */ + (traverseproc)vector_traverse, /* tp_traverse */ + 0, /* tp_clear */ + vector_richcompare, /* tp_richcompare */ + offsetof(vector_t, in_weakreflist), /* tp_weaklistoffset */ + vector_iter, /* tp_iter */ + 0, /* tp_iternext */ + vector_methods, /* tp_methods */ + vector_members, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + 0, /* tp_alloc */ + vector_new, /* tp_new */ +}; + +#if PY_MAJOR_VERSION >= 3 +struct PyModuleDef module_def = +{ + PyModuleDef_HEAD_INIT, + "immer_python_module", /* m_name */ + "", /* m_doc */ + -1, /* m_size */ + /module_methods, /* m_methods */ + 0, /* m_reload */ + 0, /* m_traverse */ + 0, /* m_clear */ + 0, /* m_free */ +}; +#endif + +PyMethodDef module_methods[] = { + {0, 0, 0, 0} +}; + +PyObject* module_init() +{ + if (PyType_Ready(&vector_t::type) < 0) + return nullptr; + +#if PY_MAJOR_VERSION >= 3 + auto m = PyModule_Create(&module_def); +#else + auto m = Py_InitModule3("immer_python_module", module_methods, ""); +#endif + if (!m) + return nullptr; + + if (!empty_vector) + empty_vector = make_vector(); + + Py_INCREF(&vector_t::type); + PyModule_AddObject(m, "Vector", (PyObject*) &vector_t::type); + return m; +} + +} // anonymous namespace + +extern "C" { +#if PY_MAJOR_VERSION >= 3 +PyMODINIT_FUNC PyInit_immer_python_module() +{ + return module_init(); +} +#else +PyMODINIT_FUNC initimmer_python_module() +{ + module_init(); +} +#endif +} |