xtuples 1.0.4

No project description provided

xtuples

---

Table of Contents

• Installation
• Overview
• Performance
• License

Installation

pip install xtuples

Overview

xtuples is designed to make functional programming easier in Python.

In particular, it is designed to enable one to mimic the function pipelines seen in languages like f#, but using method chaining.

The two key constructs are:

• xtuples.iTuple: a tuple sub-class equipped with methods like .map() .filter() and .fold().

• xuples.nTuple.decorate: a decorator to inject .pipe() .partial() and a dict of user defined methods into NamedTuples (as they can only have a single base class, this - in an albeit somewhat hacky manner - allows us to define re-usable method interfaces for named tuples).

Taken together, these tend to lead us away from inheritance, and more towards composition: to a code base comprised entirely of either free functions, or (immutable) data structures implemented using either of the above.

Worth highlighting is the compatibility this promotes with JAX, an auto-grad / machine learning framework from the Google Brain / Deepmind folks.

First, with xtuples, all our data structures are kinds of tuple, so JAX can take derivatives of / through all of our data structures without any further work (though we occasionally have to pipe iTuple -> tuple when passing into an optimiser).

Second, whilst JAX is designed with the (somewhat opinionated) assumption that user functions are pure (without side effects), because all of our data structures are immutable, an xtuples code base will already tend to be comprised of pure functions by default (so will generally require very little further refactoring to be JAX compliant).

Performance

Performance using xtuples is generally not worse than a canonical equivalent implementation, and can sometimes be significantly better.

iTuple

For instance, iTuple is simply a subclass of the built-in tuple, so has very similar performance characteristics.

Creation

Creation is slightly slower than for an equivalent length list:

%timeit xtuples.iTuple.range(10 ** 2)
%timeit list(range(10 ** 2))

1.56 µs ± 9.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
588 ns ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

%timeit xtuples.iTuple.range(10 ** 3)
%timeit list(range(10 ** 3))

11.9 µs ± 128 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
7.97 µs ± 60.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit xtuples.iTuple.range(10 ** 4)
%timeit list(range(10 ** 4))

132 µs ± 1.51 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
89.6 µs ± 817 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%timeit xtuples.iTuple.range(10 ** 6)
%timeit list(range(10 ** 6))

40.9 ms ± 1.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
24.5 ms ± 424 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Memory

Whereas memory usage (comparable for small sizes), gets increasingly more efficient with size:

memory = {}
for i in range(5):
    memory[i] = dict(
        iTuple=asizeof(xtuples.iTuple.range(10 ** i)),
        list=asizeof(list(range(10 ** i))),
    )
memory

{0: {'iTuple': 160, 'list': 88},
 1: {'iTuple': 232, 'list': 448},
 2: {'iTuple': 952, 'list': 4048},
 3: {'iTuple': 8152, 'list': 40048},
 4: {'iTuple': 80152, 'list': 400048}}

ex_iTuple = xtuples.iTuple.range(100)
ex_list = list(range(100))
ex_range = range(100)

Iteration & Indexing

Iteration is very similar:

%timeit for x in ex_iTuple: pass
%timeit for x in ex_list: pass

764 ns ± 4.57 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
721 ns ± 24.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

And whilst elementwise indexing is clearly slower:

%timeit for i in range(100): ex_iTuple[i]
%timeit for i in range(100): ex_list[i]

18.6 µs ± 240 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.84 µs ± 75.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

And so is slice indexing:

%timeit ex_iTuple[10:20]
%timeit ex_list[10:20]

667 ns ± 10.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
93.9 ns ± 0.998 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

It is worth noting that per element indexing is not all that common using xtuples (as the canonical implementation is much more likely to use .map() and co).

Function application

Elementwise function application with .map() is much faster than the equivalent loop or list comprehension:

add_2 = functools.partial(operator.add, 2)

def f_loop_map(f, l):
    res = []
    for v in l:
        res.append(f(v))
    return res

%timeit ex_iTuple.map(add_2)
%timeit f_loop_map(add_2, ex_list)
%timeit [add_2(x) for x in ex_list]
%timeit list(map(add_2, ex_list))

5.57 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
8.33 s ± 248 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
5.96 s ± 181 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
5.12 s ± 609 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

As is elementwise filtering:

def f_loop_filter(f):
    res = []
    for i in ex_list:
        if f(i):
            res.append(i)
    return res

f = lambda x: x % 2 == 0

%timeit ex_iTuple.filter(f)
%timeit f_loop_filter(f)
%timeit [v for v in ex_list if f(v)]

15.2 µs ± 41.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
6.68 s ± 139 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
7.13 s ± 113 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

And, so are both fold and cumulative fold:

def f_loop_fold():
    acc = 0
    for i in ex_list:
        acc = operator.add(acc, i)
    return acc

%timeit ex_iTuple.fold(operator.add)
%timeit f_loop_fold()

3.11 µs ± 48.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
4.87 s ± 89.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

So, as mentioned below, the answer to the poor .append() performance is just to use .foldcum() instead:

def f_loop_foldcum():
    res = []
    acc = 0
    for i in ex_list:
        acc = operator.add(acc, i)
        res.append(acc)
    return res

%timeit ex_iTuple.foldcum(operator.add)
%timeit f_loop_foldcum()

5.91 µs ± 19 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
15.2 s ± 1.67 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

Append

Appending is much slower, which is clearly to some extent a 'gotcha'.

%timeit ex_iTuple.append(1)
%timeit ex_list.append(1)

1.56 µs ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
69.3 ns ± 6.18 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Having said that, the canonical xtuples implementation is much more likely to use .map() .foldcum() or similar than .append().

And, as we've already seen, .map() and .foldcum() are much faster than the for-loop & append() implementations (so just do that instead - I personally also find it much more readable).

Prepend / Extend

Prepending to the tuple is much faster than with the list, though the relevant comparison is probably a deque (given that list is not at all optimised for left-append):

%timeit ex_iTuple.prepend(1)
%timeit ex_list.insert(0, 1)

1.44 µs ± 11 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
109 ms ± 10.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Extend is somewhat slower (but is nowhere near as bad as append):

%timeit xtuples.iTuple.range(100).extend([1])
%timeit xtuples.iTuple.range(100).extend(list(range(100)))
%timeit list(range(100)).extend([1])
%timeit list(range(100)).extend(list(range(100)))

3.93 µs ± 32.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
5.58 µs ± 43.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
769 ns ± 8.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.48 µs ± 19 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

And flatten is much faster:

ex_iTuple_nested = ex_iTuple.map(lambda v: [v])
ex_list_nested = [[v] for v in ex_list]

def f_loop_flatten(l):
    for v in l:
        yield from v

%timeit ex_iTuple_nested.flatten()
%timeit list(f_loop_flatten(ex_list_nested))
%timeit list(itertools.chain(*ex_list_nested))

5.38 µs ± 81.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
29.5 s ± 1.14 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
1min 19s ± 14.9 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

Summary

Overall, iTuple performance and memory usage is comparable - if not better - than a raw list.

The one clear weakness is .append() - however, the canonical xtuples implementation would use .map() .foldcum() etc. instead (which are actually faster than the equivalent .append() implementation).

Named Tuple

nTuple does not (in comparison to iTuple) define a base class for us to sub-class.

Rather, it provides a decorator - nTuple.decorate - that adds .pipe() .partial() and a dict of user defined methods to a given NamedTuple.

As such, performance is essentially just that of built-in NamedTuples (ie. generally very strong).

@xtuples.nTuple.decorate(
    update_x = lambda self, x: self._replace(x=x), 
    update_s = lambda self, s: self._replace(s=s),
)
class Example(typing.NamedTuple):
    x: int
    s: str
    
class Example_Cls:
    x: int
    s: str
    
    def __init__(self, x, s):
        self.x = x
        self.s = s

@dataclasses.dataclass(frozen=True, eq=True)
class Example_DC:
    x: int
    s: str
    
ex_nTuple = Example(1, "a")
ex_dict = dict(x=1, s="a")
ex_cls = Example_Cls(1, "a")
ex_dc = Example_DC(1, "a")

NOTE, re-registering: Example

For instance, NamedTuples are significantly more memory efficient than any of the possible alternatives:

dict(
    nTuple=asizeof(ex_nTuple),
    dict=asizeof(ex_dict),
    cls=asizeof(ex_cls),
    dataclass=asizeof(ex_dc),
)

{'nTuple': 144, 'dict': 432, 'cls': 352, 'dataclass': 352}

%timeit Example(1, "a")
%timeit dict(x=1, s="a")
%timeit Example_Cls(1, "a")
%timeit Example_DC(1, "a")

257 ns ± 8.92 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
111 ns ± 1.53 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
209 ns ± 2.58 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
443 ns ± 3.05 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Whilst providing comparable (if not slightly faster) field access times:

%timeit ex_nTuple.x
%timeit ex_nTuple[0]
%timeit ex_dict["x"]
%timeit ex_cls.x
%timeit ex_dc.x

27.7 ns ± 0.303 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
25.1 ns ± 0.0815 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
29.7 ns ± 0.181 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
30.3 ns ± 0.492 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
34.9 ns ± 0.125 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Writes are, however, slower - the price we pay for immutability (but are still notably faster than the frozen dataclass equivalent):

%timeit ex_dict["x"] = 1
%timeit ex_cls.x = 1
%timeit ex_nTuple._replace(x = 1)
&timeit ex_nTuple.update_x(x)
%timeit ex_nTuple.update(x=1)
%timeit dataclasses.replace(ex_dc, x=1)

32.4 ns ± 0.467 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
43.8 ns ± 0.524 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
735 ns ± 5.93 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.03 µs ± 3.35 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.28 µs ± 4.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Like frozen dataclasses, NamedTuples are conveniently hashable (in comparison to dicts, for instance, which aren't), and do so based on value (versus standard classes which use object ids by default):

dict(
    nTuple= hash(ex_nTuple) == hash(Example(1, "a")),
    cls= hash(ex_cls) == hash(Example_Cls(1, "a")),
    dataclass= hash(ex_dc) == hash(Example_DC(1, "a")),
)

{'nTuple': True, 'cls': False, 'dataclass': True}

This is particularly useful in combination with iTuple, which is also hashable (making combinations of the two recursively hashable):

@xtuples.nTuple.decorate
class Example_Nested(typing.NamedTuple):
    x: int
    s: str
    
    it: xtuples.iTuple
    
hash(Example_Nested(1, "s", xtuples.iTuple())) == hash(Example_Nested(1, "s", xtuples.iTuple()))

True

Finally, sorting is both provided by default (again, in comparison to dicts and classes), and works as one would expect (ie. by the first field, then the second field, etc.):

xtuples.iTuple([
    Example(2, "a"),
    Example(1, "b"),
    Example(1, "a"),
]).sort()

iTuple(Example(x=1, s='a'), Example(x=1, s='b'), Example(x=2, s='a'))

License

xtuples is distributed under the terms of the MIT license.