void* as elements of a set?

[Simon King]

Hi!

I'd like to create a dictionary that is indexed by pairs of integers, and whose values are sets whose elements are pointers.

One possibility is to convert the pointers (void*) to a numerical data type, such as size_t, that can be put into a set. But I wonder if it is really safe to use. So, my first bunch of questions: Is it guaranteed that on all machines a size_t is large enough to store a void*? I.e., if ptr is a pointer, is it possible to reconstruct ptr from <size_t>ptr? If not, what should I use instead of size_t?

Or, second bunch of questions: Is it possible to implement what I want (a dictionary indexed by pairs of integers yielding sets of pointers) in a different way, say, by using cython's c++ capabilities? If yes, how?

Best regards,
Simon

[Robert Bradshaw]

On Sat, Jan 24, 2015 at 6:48 AM, Simon King <simon...@uni-jena.de> wrote:
> Hi!
>
> I'd like to create a dictionary that is indexed by pairs of integers, and
> whose values are sets whose elements are pointers.
>
> One possibility is to convert the pointers (void*) to a numerical data type,
> such as size_t, that can be put into a set. But I wonder if it is really
> safe to use. So, my first bunch of questions: Is it guaranteed that on all
> machines a size_t is large enough to store a void*? I.e., if ptr is a
> pointer, is it possible to reconstruct ptr from <size_t>ptr? If not, what
> should I use instead of size_t?

Technically, you need intptr_t, though practically any system modern
enough to have (C99) intptr_t is likely to have a memory addressing
scheme such that sizeof(size_t) == sizeof(intptr_t).

> Or, second bunch of questions: Is it possible to implement what I want (a
> dictionary indexed by pairs of integers yielding sets of pointers) in a
> different way, say, by using cython's c++ capabilities? If yes, how?

You could always introduce your own wrapper of void*(s) with a custom
hash and equality operator. Or implement the dictionary yourself (as
in https://github.com/sagemath/sagelib/blob/master/sage/structure/coerce_dict.pyx).

- Robert

[Simon King]

Dear Robert,

Am Samstag, 24. Januar 2015 18:04:53 UTC+1 schrieb Robert Bradshaw:

On Sat, Jan 24, 2015 at 6:48 AM, Simon King <simon...@uni-jena.de> wrote:
> I'd like to create a dictionary that is indexed by pairs of integers, and
> whose values are sets whose elements are pointers.

Technically, you need intptr_t, though practically any system modern
enough to have (C99) intptr_t is likely to have a memory addressing
scheme such that sizeof(size_t) == sizeof(intptr_t).

Thank you! So, to be on the safe side, I'll use intptr_t.
 

> Or, second bunch of questions: Is it possible to implement what I want (a
> dictionary indexed by pairs of integers yielding sets of pointers) in a
> different way, say, by using cython's c++ capabilities? If yes, how?

You could always introduce your own wrapper of void*(s) with a custom
hash and equality operator.

I'd prefer to not write my own custom dictionary and set implementations from scratch. Can one not use C++'s std::map and std::set in cython? I was wondering how...

Best regards,
Simon

[Robert Bradshaw]

See https://github.com/cython/cython/blob/master/tests/run/libcpp_all.pyx
for uses of std::map and std::set. The extra comparison template
parameter is not supported, you'd have to re-wrap it for that.

[Nils Bruin]

On Saturday, January 24, 2015 at 9:04:53 AM UTC-8, Robert Bradshaw wrote:

You could always introduce your own wrapper of void*(s) with a custom
hash and equality operator. Or implement the dictionary yourself (as
in https://github.com/sagemath/sagelib/blob/master/sage/structure/coerce_dict.pyx).

Simon is fully aware of it because he helped testing and debugging it, but note that by now the implementation of those dictionaries in sage is considerably different than what you're pointing to:

 https://github.com/sagemath/sage/blob/master/src/sage/structure/coerce_dict.pyx

The implementation now is using open addressing, just as python's own dictionaries, and the performance is close to python's dict as well. We had some issues, since the tp_traverse and tp_clear generated by cython aren't correct (cython doesn't know which objects in the dict store to visit), so we have to hack those in after cython has executed its PyType_Ready.

 

- Robert

[Sturla Molden]

On 24/01/15 18:04, Robert Bradshaw wrote:

> Technically, you need intptr_t, though practically any system modern
> enough to have (C99) intptr_t is likely to have a memory addressing
> scheme such that sizeof(size_t) == sizeof(intptr_t).

Python has Py_inptr_t and Py_uintptr_t.

NumPy has npy_intp and npy_uintp. They are named intp_t and uintp_t if
you cimport them from numpy.

All of these integers have the size of void*. That is guaranteed by
Python and NumPy, but they are not a part of the C standard. However,
Cython cannot be used independent of Python, so this should not be a
problem here.


Sturla

[Sturla Molden]

On 24/01/15 15:48, Simon King wrote:

> One possibility is to convert the pointers (void*) to a numerical data
> type, such as size_t,

size_t is sufficiently large to index the largest segment, it does not
always have the size of void*.

On x86 the maximum address space is 2**48 bytes but the maximum segment
length is 2**32 bytes. So theoretically an x86 system could have a 64
bit void* but only an 32 bit size_t. However every OS is use hides this
by truncating the virtual address space to 2**32 bytes. So the only
thing we see to this non-flat address space in x86 is 32-bit servers
with more than 4 GB ram. But theoretically someone might change this and
provide us with a Linux kernel that exposes the full capabilities of the
x86 processor. Processors with non-flat address spaces could also show
up in the future, though it is less likely now that 64 bit is the norm.

However there is an important thing to learn from this: To make portable
C code, (1) never index with intptr_t and (2) never store a pointer in a
long or a size_t.


Sturla

[Sturla Molden]

On 24/01/15 18:04, Robert Bradshaw wrote:

> Technically, you need intptr_t, though practically any system modern
> enough to have (C99) intptr_t is likely to have a memory addressing
> scheme such that sizeof(size_t) == sizeof(intptr_t).

In C++ intptr_t and uintptr_t are optional in stdint.h. They are not
required to be there. For that reason it is better to use the Python
equivalents in Cython code.

Sturla

[Simon King]

Dear Robert, dear all,

thank you for pointing me to Py_intptr_t!
A duckduckgo-search taught me to do

    cdef extern from "Python.h":
        ctypedef int Py_intptr_t

But is that really correct? Can one not cimport Py_intptr_t from somewhere?

Am Samstag, 24. Januar 2015 21:13:28 UTC+1 schrieb Robert Bradshaw:

See https://github.com/cython/cython/blob/master/tests/run/libcpp_all.pyx
for uses of std::map and std::set. The extra comparison template
parameter is not supported, you'd have to re-wrap it for that.

Perhaps I should give a small example of what I want to do.

Here is a container "Dict2" that wraps "dict", and whose get/setitem show the behaviour that I want to achieve:

cdef class Dict2:
    cdef dict data
    def __init__(self):
        self.data = dict()
    def __getitem__(self,key):
        return self.data[key]
    def __setitem__(self, key,val):
        cdef set S = self.data.setdefault(key, set())
        S.add(val)

Here is a container "Dict" that wraps a std::map and shows equivalent behaviour:

from libcpp.map cimport map as cmap
from libcpp.set cimport set as cset
from libcpp.pair cimport pair
from cython.operator cimport dereference as deref

ctypedef pair[int,int] intpair
ctypedef cset[int] intset
ctypedef cmap[intpair, intset] pair2set

cdef class Dict:
    cdef pair2set data
    def __dealloc__(self):
        self.data.clear()
    def __getitem__(self, key):
        # Why does the following line NOT compile, ...
        #cdef pair2set.iterator iter = self.data.find(<intpair>key)
        # even though the following line DOES compile??
        cdef cmap[intpair, intset].iterator iter = self.data.find(<intpair>key)
        if iter != self.data.end():
            # Why is deref() needed? I expected that, similar to using a <intpair*>,
            # the member ".second" would be available without dereferencing.
            return deref(iter).second
        raise IndexError(key)

    def __setitem__(self, key, val):
        cdef intpair K = <intpair>key
        # If K is an unknown key, then self.data[K] returns the empty set. Why
        # is no error raised?
        cdef intset S = self.data[K]
        S.insert(<int>val)
        # The previous line does NOT change the content of self.data[K], even if K is a
        # known key. Why? I would like to do the insertion in-place, so that
        # the following line is only needed when K has not been used before.
        self.data[K] = S

Note the questions that I ask in the code comments.

What surprises me most: Dict is *much* slower than Dict2. That may not be a surprise for __setitem__, since I couldn't simply add to a value in-place. But __getitem__ is much slower as well, even though one might think that knowing the types for keys and values should result in better performance.
Why is that? Is Python's dict so good, or is my usage of std::map and std::set so bad? Is it reasonable to keep using "dict" rather than "map<pair<int,int>,set<void*>>".

Best regards,
Simon

[Simon King]

Am Sonntag, 25. Januar 2015 00:32:49 UTC+1 schrieb Simon King:

    def __setitem__(self, key, val):

        cdef intpair K = <intpair>key

        cdef intset S = self.data[K]
        S.insert(<int>val)

        self.data[K] = S

I just realise that the following does the in-place change that I want, and is *faster*  than what I do in Dict2.__setitem__:

    def __setitem__(self, key, val):
        self.data[<intpair>key].insert(<int>val)

So, do you see a way to make __getitem__ faster, too?
Best regards,
Simon

 

[Simon King]

Perhaps unordered_map would be better for me than map?

But then, how to use unordered_map in cython?
how-to-use-unordered-map-in-cython is supposed to explain it, but the recipes proposed there do not work for me (neither

  from libcpp.unordered_map cimport unordered_map

nor

    cdef extern from "<unordered_map>" namespace "std::tr1": ...

compile).

Cheers,
Simon

[Simon King]

Dear Sturla, Robert and Nils,

meanwhile I have learned how to use map, unordered_map and multimap via cython. Note that stackoverflow gives some hints for unordered_map that don't work.

In the small experiments that I did, dict was by no means slow in comparison, and since it is easier to use, I will keep using it for now.

But then, there is one question that hasn't been answered yet:

Am Sonntag, 25. Januar 2015 00:32:49 UTC+1 schrieb Simon King:

A duckduckgo-search taught me to do

    cdef extern from "Python.h":
        ctypedef int Py_intptr_t

But is that really correct? Can one not cimport Py_intptr_t from somewhere?

Perhaps I misunderstand: Isn't `ctypedef int Py_intptr_t` identifying Py_intptr_t with int, which is what we want to avoid?

Best regards,
Simon

 

[Nils Bruin]

On Sunday, January 25, 2015 at 5:44:29 AM UTC-8, Simon King wrote:

    cdef extern from "Python.h":

        ctypedef int Py_intptr_t

But is that really correct? Can one not cimport Py_intptr_t from somewhere?

Perhaps I misunderstand: Isn't `ctypedef int Py_intptr_t` identifying Py_intptr_t with int, which is what we want to avoid?

That looks to me like one of cython's "close enough" type declarations. Note that it's "extern", so this definition does not get fed to the C compiler. It will get its definition (indirectly) from pyport.h, where quite a bit of effort goes into defining Py_intptr_t correctly, providing workarounds for platforms that do not offer uintptr_t and intptr_i.

[Sturla Molden]

std::unordered_map is a part of C++11 standard. You thus need to tell the
C++ compiler to use this standard instead of C++98 when compiling the
Cython code.

I.e. when using g++ or clang++, have "-std=c++11" in The CXXFLAGS
evironment variable or pass it as one of the "extra_compile_flags" in
setup.py. Or have this comment in your Cython file:

# distutils: extra_compile_args = -std=c++11

i don't remeber if Cython has std::unordered_map in its libcpp includes.
But if it does not it should look like the declaration of std::map.

Sturla

[Sturla Molden]

This is indeed correct:

cdef extern from "Python.h":
ctypedef int Py_intptr_t

ctypedef unsigned int Py_uintptr_t

This is correct too:

cdef extern from "Python.h":
ctypedef long Py_intptr_t
ctypedef unsigned long Py_uintptr_t

Cython does not need to know the real size of Py_intptr_t because it
generates C. Cython does generate not machine code, and as such it does not
care about the binary interface. That is deferred to the C compiler.

When the C compiler ses the declaration

Py_intptr_t foo;

in the generated C code it knows what to do.

Cython's ctypedef just informs Cython of the C API ("programming
interface"), i.e. that Py_intptr_t is an integer type of some sort. It does
not say anything about the C ABI ("binary interface"). Cython just needs to
know so much about the type that it can generate the correct calls to the
Python C API.

It is for the same reason it is ok to skip fields or reorder them when
declaring an external struct in Cython. Cython just needs to be informed of
the field names we are going to use and "roughly their type".

Sturla

[Sturla Molden]

On 25/01/15 01:35, Simon King wrote:

> Perhaps unordered_map would be better for me than map?

std::map is a binary search tree. It has best case complexity O(log n)
and worst case complexity O(n) for looking up an entry.

std::unordered_map is a hash table like Python's dict. It has always
complexity O(n) for looking up an entry.

Nevertheless, these are the complexities, not the absolute performance.
std::map is usually faster than std::unordered_map for a number of
reasons, but cache locality is particularly important.

std::map breaks down to O(n) in the same situation as Quicksort becomes
O(n**2): sorted or nearly sorted data. You can balance std::map and
ensure O(log n) lookup by generating it from shuffled data.

std::set and std::unordered_set differ in the same way.

A decision was made in the original STL to make std::map and std::set
binary search trees instead of hash tables, because under most
circumstances they performs better. You see the same in databases too,
where binary search trees are often preferred to hashtables. A binary
search tree also allows for an efficient structured search ("find all
elements less than this value"), but hash tables do not.

But try both versions and see which one performs better.
std::unordered_map and std::unordered_set are modelled after Python's
dict and set, so they should perform equally well.

In my own experience, the only STL container that can really help
speed-wise is std::vector, because it can both behave like a Python list
and a C array. It can give O(1) item access without Python overhead like
a C array, but appends are amortized O(1) like a Python list.

std::map and std::set can be useful for releasing the GIL, but they are
often not much faster than dict and set if you don't care about the GIL.

Sturla

[Simon King]

Hi Sturla,

Am Sonntag, 25. Januar 2015 21:03:29 UTC+1 schrieb Sturla Molden:

std::unordered_map is a part of C++11 standard. You thus need to tell the
C++ compiler to use this standard instead of C++98 when compiling the
Cython code.

...

i don't remeber if Cython has std::unordered_map in its libcpp includes.
But if it does not it should look like the declaration of std::map.

I couldn't find it in libcpp. But it is in boost, so, the following did the trick (even though I did *not*  C++11).

cdef extern from "<boost/unordered_map.hpp>" namespace "boost":
    cdef cppclass unordered_map[K, T]: # K: key_type, T: mapped_type
        cppclass iterator:
            pair& operator*()
            bint operator==(iterator)
            bint operator!=(iterator)
        unordered_map()
        bint empty()
        size_t size()
        iterator begin()
        iterator end()
        iterator find(K)
        void clear()
        size_t count(K)
        T& operator[](K)

And multimap doesn't seem to be in libcpp either, but the following works:

cdef extern from "<map>" namespace "std":
    cdef cppclass multimap[K, T]: # K: key_type, T: mapped_type
        cppclass iterator:
            pair[K,T]& operator*()
            iterator operator++()
            bint operator==(iterator)
            bint operator!=(iterator)
        multimap()
        bint empty()
        size_t size()
        iterator begin()
        iterator end()
        iterator find(K)
        iterator insert(pair[K, T])
        void erase(iterator)
        pair[iterator, iterator] equal_range(K)
        void clear()
        size_t count(K)

It currently seems that I will not use the C++ containers in my code.
But just out of curiosity: If ptr is a pointer to T, and T has a member bla, then "ptr.bla" is available. But if iter is (in the above examples) an iterator of pair[K,T], then iter.first and iter.second are *not* available. One seemingly needs to do "dereference(iter).first". Why is that?

Best regards,
Simon

[Simon King]

Dear Sturla,

Am Sonntag, 25. Januar 2015 22:25:51 UTC+1 schrieb Sturla Molden:

A decision was made in the original STL to make std::map and std::set
binary search trees instead of hash tables, because under most

circumstances they performs better. ... In my own experience, the only STL container that can really help

speed-wise is std::vector, because it can both behave like a Python list
and a C array. It can give O(1) item access without Python overhead like
a C array, but appends are amortized O(1) like a Python list.

The whole discussion (and also some comments on sage-devel) made me think whether I should fundamentally change the data types of my current project (standard basis computations for very highly non-commutative algebra quotients using a non-commutative version of the F5 algorithm).

The elements are formed by terms which are linearly ordered, and each term is a pair "monomial--coefficient".
Do I understand correctly that std::vector is not good for insertions? But it may be a good idea to implement an element as "std::map[monomial_type,coefficient_type]", since that is sorted, too, and I think insertions are more or less affordable, aren't they?

But then, I would need that the map sorts its contents by a comparison function for monomial_type that can be chosen at run-time (there are different monomial orderings, and it isn't clear at compile-time which one to use). C++ allows that. Is that aspect adopted by Cython, yet?

For now, I will keep my existing implementation (where elements are pointered lists of terms). At some point, advanced examples will point me to bottlenecks of the implementation, and then I can decide what to do. Not now.

Best regards,
Simon

[Sturla Molden]

On 25/01/15 23:08, Simon King wrote:

> The elements are formed by terms which are linearly ordered, and each
> term is a pair "monomial--coefficient".

> Do I understand correctly that std::vector is not good for insertions?

std::vector<T>::push_back is amortized O(1) and very fast.

Insertions in the middle is O(n).

> But it may be a good idea to implement an element as
> "std::map[monomial_type,coefficient_type]", since that is sorted,
> too,

No it is not a good idea, because if the elements are ordered when you
add them to your std::map, the lookup time will be O(n) instead of O(log
n). A binary search tree is ordered, but should not be created from
already ordered data.

Add the terms to the map in random order, use a std::vector, or use
std::unordered_map.

std::vector will probably be the fastest container here.



Sturla

[Sturla Molden]

On 25/01/15 22:46, Simon King wrote:

> But if iter is (in the above examples)
> an iterator of pair[K,T], then iter.first and iter.second are *not*
> available. One seemingly needs to do "dereference(iter).first". Why
is that?

Probably because the C++ compiler gets angry if Cython generates
iter->first instead of (*iter).first.


Sturla

[Simon King]

Dear Sturla,

Am Montag, 26. Januar 2015 01:15:15 UTC+1 schrieb Sturla Molden:

std::vector<T>::push_back is amortized O(1) and very fast.

Insertions in the middle is O(n).

I am afraid the insertions that I need generally *are* in the middle.

Anyway, I will keep using my pointered lists. In most cases, I know the term after which I have to insert, so, insertion is O(1). If applications will point me to bottlenecks, I can still change to a different data structure.

Best regards,
Simon

[Sturla Molden]

Insertions in the middle of a sequence is ill-posed regardless of what
linear container you use.

A linked list can insert an element anywhere in O(1) time, but looking up
the middle element is an O(n) operation.

A vector can insert an element in the middle in O(n) time, but looking up
the middle element is O(1).

In both cases you have O(n) complexity.


A hash table can solve this problem in O(1) time, however.


Sturla