Author Archives: david

Reality is a countably infinite Sierpiński cube

I was thinking out loud on Twitter about what weird beliefs I hold, after realising (more or less as I was writing it) that my philosophical positions are practically banal (at least to anyone who has thought about these issues a bit, whether or not they agree with me).

I came up with a couple, but probably the most interesting (if very very niche) that I thought of is that one true and accurate mathematical model of reality is  time cube a closed, connected, subset of the countably infinite Sierpinski cube.

I consider this opinion to be not that weird and more importantly obviously correct, but I’m aware that this is a niche opinion, but hear me out.

Before we start, a quick note on the nature of reality. I am being deliberately imprecise about what I mean by “reality” here, and basically mean “any physical system”. This could be “life the universe and everything” and we are attempting to solve physics, or it could be some toy restricted physical system of interest and we are trying to nail down its behaviour. This post applies equally well to any physical system we want to be able to model.

Consider an experiment. Let’s pretend we can have deterministic experiments for convenience – you can easily work around the impossibility by making countably infinitely many copies of the experiment and considering each of them to be the answer you got the nth time you ran the experiment.

Also for simplicity we’ll assume that experiments can only have one of two outcomes (this is no loss of generality as long as experiments can only have finitely many outcomes – you just consider the finitely many experiments of the form “Was the outcome X?” – and if they have infinitely many outcomes you still need to ultimately make a finite classification of the result and so can consider the experiment composed with that classification).

There are three sensible possible outcomes you could have here:

  • Yes
  • No
  • I don’t know, maybe?

Physical experiments are inherently imprecise – things go wrong in your experiment, in your setup, in just about every bloody thing, so set of experiments whose outcome will give you total certainty is implausible and we can ignore it.

Which leaves us with experiments where one of the answer is maybe. It doesn’t matter which answer the other one is (we can always just invert the question).

So we’ve run an experiment and got an answer. What does that tell us about the true state of reality?

Well whatever reality is we must have some notion of “an approximate region” – all of our observation of reality is imprecise, so there must be some notion of precision to make sense of that.

So reality is a topological space.

What does the result of a physical experiment tell us about the state of reality?

Well if the answer is “maybe” it doesn’t tell us anything. Literally any point in reality could be mapped to “maybe”.

But if the answer is yes then this should tell us only imprecisely where we are in reality. i.e. the set of points that map to yes must be an open set.

So an experiment is a function from reality to {yes, maybe}. The set of points mapping to yes must be an open set.

And what this means is that experiments are continuous functions to the set {yes, maybe} endowed with the Sierpiński topology. The set {yes} is open, and the whole set and the empty set are open, but nothing else is.

Now let’s postulate that if two states of reality give exactly the same answer on every single experiment, they’re the same state of reality. This is true in the same sense that existing is the thing that reality does – a difference that makes no difference might as well be treated as if it is no difference.

So what we have is the following:

  1. Any state of reality is a point in the cube \(S^E\) where \(E\) is the set of available experiments and \(S = \{\mathrm{yes}, \mathrm{maybe}\}\).
  2. All of the coordinate functions are continuous functions when \(S\) is endowed with the Sierpinski topology.

This is almost enough to show that reality can be modelled as a subset of the Sierpinski cube, not quite: There are many topologies compatible with this – reality could have the discrete topology.

But we are finite beings. And what that means is that any given point in time we can have observed the outcome of at most finitely many experiments.

Each of these experiments determine where we are only in the open set of some coordinate in our cube, thus the set that the experiments have determined us to be in is an intersection of finitely many open sets in the product topology on that cube, and thus is open in that topology.

Therefore the set of states of reality that we know we are in is always an open set in the product topology. So this is the “natural” topology on reality.

So reality is a subset of a Sierpiński cube. We now have to answer two questions to get the rest of the way:

  • How many dimensions does the cube have?
  • What sort of subset is it?

The first one is easy: The set of experiments we can perform is definitely infinite (we can repeat a single experiment arbitrarily many times). It’s also definitely countable, because any experiment we can perform is one we can describe (and two experiments are distinct only up to our ability to describe that distinction), and there are only countably many sentences.

So reality is a subset of the countably infinite dimensional Sierpiński cube.

What sort of subset?

Well that’s harder, and my arguments for it are less convincing.

It’s probably not usually the whole set. It’s unlikely that reality contains a state that is just constantly maybe.

It might as well be a closed set, because if it’s not we can’t tell – there is no physical experiment we can perform that will determine that a point in the closure of reality is not in reality, and it would be aesthetically and philosophically displeasing to have aphysical states of reality that are approximated arbitrarily well.

In most cases it’s usually going to be a connected set. Why? Well, because you’re “in” some state of reality, and you might as well restrict yourself to the path component of that state – if you can’t continuously deform from where you are to another state, that state probably isn’t interesting to you even if it in some sense exists.

Is it an uncountable subset of the Sierpinski cube? I don’t know, maybe. Depends on what you’re modelling.

Anyway, so there you have it. Reality is a closed, connected, subset of the countably infinite dimensional Sierpiński cube.

What are the philosophical implications?

Well, one obvious philosophical implication is that reality is compact, path connected, and second countable, but may not be Hausdorff.

(You should imagine a very very straight face as I delivered that line)

More seriously, the big implication for me is on how we model physical systems. We don’t have to model physical systems as the Sierpiński cube. Indeed we usually won’t want to – it’s not very friendly to work with – but whatever model we choose for our physical systems should have a continuous function (or, really, a family of continuous functions to take into account the fact that we fudged the non-determinism of our experiments) from it to the relevant Sierpiński cube for the physical system under question.

Another thing worth noting is that the argument is more interesting than the conclusion, and in particular the specific embedding is more important that the embedding exists. In fact every second countable T0 topological space embeds in the Sierpinski cube, so the conclusion boils down to the fact that reality is a T0, second countable, compact, and connected (path connected really) topological space (which are more or less the assumptions we used!).

But I think the specific choice of embedding matters more than that, and the fact that we the coordinates correspond to natural experiments we can run.

And, importantly, any decision we make based on that model needs to factor through that function. Decisions are based on a finite set of experiments, and anything that requires us to be able to know our model to more precision than the topology of reality allows us to is aphysical, and should be avoided.

A statement of philosophical principles

Epistemic status: This is my philosophy. There are many like it, but this one is mine. It is not anything especially unusual or particularly sophisticated.

I’ve noticed in a couple of discussions recently that my philosophical positions are both somewhat opposed to what might be considered normal (at least among non-philosophers) and may seem internally contradictory.

It also occurred to me that I’ve never really properly explained this to people, and that it might be worth writing up a short position statement.

So, here is the philosophical basis on which I live my life. You can think of it as a rather extreme combination of moral relativism and mathematical formalism.

  1. Words, and the concepts behind them, are made up and have no objective meaning or basis.
  2. Statements cannot thus really be “true” or “false” (though they may be deductively true in the context of a certain set of premises and logic).
  3. Reality exists only because if it doesn’t then exist is not a useful word, so existing is defined mostly by reference as the thing that reality does.
  4. Perception of reality is intrinsically flawed and what we perceive may be arbitrarily far from what “really” exists (if we accept our senses, then empiricism shows us that it’s quite far. If we don’t accept our senses, we’re already there).
  5. We are probably not ever going to be capable of accurately modelling or predicting the universe. Even if it’s in principle possible we’re probably not smart enough.
  6. All value systems are subjective and culturally determined.
  7. Morality is some complex mix of value system and prediction, so it’s certainly subjective and culturally determined, but also probably beyond our ability to actually formalise in any useful way even once we’ve already pinned down a value system.

…but if we take any of that too seriously we’ll never get anything useful done, and even if there’s no objective value to getting useful things done, subjectively I’m quite fond of it, so…

  1. We should use words in a way that achieves a broad consensus and seems to be useful for talking about what we observe.
  2. Accept a reasonably large body of knowledge as a useful working premise, but occasionally backtrack and note that you’re explicitly doing that when it leads you astray or causes disagreements.
  3. Treat reality as if it exists in a naive objective sense, because it hurts when you don’t.
  4. Don’t worry about it too much. If there’s an all-powerful demon faking your perception of reality, there’s probably not much you can do about it. Also see previous item – that reality which you perceive exists (even if any given perception may not be valid), because otherwise exists isn’t a very useful word.
  5. We can do a surprisingly good job at our current level, and just because we can never achieve perfection doesn’t mean we shouldn’t try to improve what we’ve got.
  6. But I like mine, and it includes a term for a certain amount of forcing itself on other people (“hurting people is bad and I don’t really care if you think you have a culturally valid reason for doing it”).
  7. Doing the right thing is hard. Do the best you can. Don’t sweat the grand theory of morality too much, but pay attention when it comes up.

So as a result I temper the extreme relativist stance with a solid dose of pragmatic instrumental reasoning and pretend that I believe in philosophical naive realism because it’s much better at getting the job done than refusing to even acknowledge that such a thing as a job might exist and that it could be done if it did.

A lot of these theses are for me much like the way in which I am an atheist: I consider them to be obviously correct as a sort of “ground state” truth. It’s not that they’re necessarily right, it’s just that in the absence of evidence to the contrary they seem like a good default position, and nobody has provided evidence that I find convincing (and in some cases I’m not sure such evidence could exist even in principle). Maybe there’s a platonic realm of ideals after all, but formalism works perfectly well without it and if such a thing existed how could we possible know?

I probably got very excited and/or angsty about all this at one point as a teenager, but eventually I realised that maybe I just don’t care that much. Does it matter if the table I stubbed my toe on really exists? Does it matter if there is actually such a thing as a table? Either way it still hurts, and if I want something to eat my meals on I’m going to struggle to buy one from ikea without acknowledging the concept of a table. For most things I actually care about, life is just easier if I go along with naive realism.

But it’s important to me to understand that I’m just pretending. Particularly because it makes it much easier to acknowledge when I’m wrong (which I’m not always good at, but that’s not surprising. Just because I have a philosophy doesn’t mean I’m good at following it), and to understand where other people are coming from – politics is much easier to understand if you understand that value systems are subjective and arbitrary. No reason that I have to accept those values, mind you (my culturally determined subjective values frequently strongly prefer that I don’t), but it’s helpful to know where they could be coming from.

And in general I find there’s a certain useful humility to affirming that I have no access to any objective source of truth nor ever will, and that that’s OK.

This entry was posted in Performing philosophy without a license on by .

The politics of “I don’t know”

My politics these days are increasingly vague, because I’m increasingly uncomfortable with proposing solutions when I don’t understand the problems.

If I had actual political power, that would be one thing – I would try things and see what worked – but I don’t, so I’m left with angry shouting about why everyone fails to see that my obviously correct solution is obviously correct as my main socially acceptable option for political expression.

And I don’t know what the correct solution is.

I’m not quite at the Socrates level of knowing that I know nothing. I know a few things. Unfortunately most of the things I know are “Wow this problem is hard, huh?”

(I also know that the current brand of politics in both my countries is very bad and should be opposed. This post is more about how I’d like things to work once everything isn’t on fire)

Unfortunately “This problem is hard” seems to be literally the only thing peoples’ politics are willing to universally unite against. If a politician admits that a problem is hard and they don’t know what to do about it, they might as well start writing their resignation letter now and save the papers the effort of raking them over the coals and you the time of voting them out of office.

Here are two problems I know to be hard beyond our current ability to deal with:

  1. Centralised planning of a complex system
  2. Decentralised coordination in response to large-scale problems

If you’ll forgive the horrendous oversimplification of politics in a post complaining about the horrendous oversimplification of politics, economic left vs right wing political opinion seems to be largely a split on which one of those two things we want to deny is hard.

Either we should let the market solve everything including the things that the market can’t solve because they require individuals to act against their best interests in order to achieve a collectively better result, or we nationalise everything and the people who are an inconveniently tiny fraction of the population to worry about in our centralised planning get crushed by the system.

How should we solve both of these problems simultaneously? I don’t know.

I sometimes refer to the problem of how you get a large group of people to coordinate for their mutual benefit as the fundamental problem of civilization. Many (most?) ideologies think they have an answer to this problem, but all of the answers I’ve seen seem to be pretty bad.

Which is not to say the current compromise system is good either. In many ways we’re suffering from a blend of the worst problems of each – we can’t coordinate properly, but the giant machine of society still crushes people. To some extent we’ve compromised by each side adopting the worst excesses of the other. Massive accumulation of capital in individuals results in people happily doing their own version of centralised planning, while states generally totally fail to solve coordination problems because politicians are more concerned with soundbites that will get them reelected than the good of the country or world.

Can we do better? I don’t know. Probably. Certainly I’m going to choose to believe we can. But I think as long as we deny hard problems are hard, we’re going to keep failing to solve them.

Does this make me a centrist? I guess this makes me a centrist, so I’ve probably now outed myself to my friends (who are mostly left-wing, as am I on a lot of issues) as literally/figuratively worse than Hitler. I can’t say I’ve found most centrist politicians any more appealing than the run of the mill on either side, but maybe the problem there is politicians and the system they work in, rather than their specific politics.

Does this mean I think better things aren’t possible? No. But I do think that whatever your current politics are, if you don’t admit “I don’t know” as an answer, the way you want us to be going probably won’t get us there.

This entry was posted in Uncategorized on by .

Truth and/or Justice

Disclaimer: This post is obscure in places. I apologise for that. Reasons.

Everyone likes to think they’re the protagonist of their own story. And as a hero, we need a cause. On the left and those morally aligned with the left, that can often roughly be summed up as “Truth and Justice” (we generally leave The American Way to people who wear their underpants on the outside).

(Some people are more honest, or less moral, and instead are fighting for survival, or for self-interest. This post is not about those people. Some people are less morally aligned with the left and fight for things like purity and respect for authority too. As a devout moral relativist, I acknowledge the validity of this position, but I still struggle to take it seriously. If this is you, you may get less out of this post but the broad strokes should still apply).

Unfortunately, you can’t optimise for more than one thing. Truth and Justice is not a thing you can fight for. You can fight for truth, you can fight for justice, you can fight for a weighted sum of truth and justice, but you cannot reliably improve both at once.

Often we can ignore this problem. Truth and Justice frequently work very well together. But at some point (hopefully metaphorically) the murderer is going to turn up at your door and you’re going to have to decide whether or not to lie to them. Unless you’re prepared to go full Kant and argue that lying to protect another is unjust as well as untrue, you’ll have to make a trade off.

So what’s it going to be? Truth or Justice?

It’s not an absolute choice of course – depending on the circumstances and the results of a local cost/benefit analysis, almost all of us will sometimes choose truth, sometimes justice. and sometimes we’ll make a half-arsed compromise between the two which leaves both truth and justice grumbling but mostly unbloodied.

But I think most of us have a strong bias one way or the other. This may not be inherent – it’s probably in large part driven by factionalisation of the discourse space – but certainly among my main intellectual and political influences there’s at least one group who heavily prioritises truth and another who heavily prioritises justice.

That’s not to say we don’t care about the other. Caring about justice doesn’t make you a liar, caring about truth doesn’t make you heartless. It’s just that we care about both, but we care about one more.

Personally, I tend to flip flop on it. I find myself naturally aligned with truth (I hate lying, both being lied to and lying myself), but I think I’ve historically chosen to align myself with people who prefer justice, usually by denying that the trade-off exists.

But recently I’ve been feeling the pendulum swing the other way a bit. If you’ve wondered why I’ve gone quiet on a bunch of subjects, that’s part of what’s been going on.

One of the reasons I think about this a bunch is in the context of labelling.

A long time ago now I wrote “You Are Not Your Labels“, about the problem of fuzzy boundaries and how we tend to pick a particular region in the space of possibility that includes us, use a label for that region, and then defend the boundaries of that label zealously.

I still broadly stand by this. You are not your labels. I’m certainly not my labels.

But we might be.

One of the places where truth and justice play off against each other is when you’re being attacked. If you’re under fire, now is not really the time to go “Well the reality is super complicated and I don’t really understand it but I’m pretty sure that what you’re saying is not true”. Instead, we pick an approximation we can live with for now and double down on it with a high degree of confidence.

There probably isn’t “really” such a thing as a bisexual (I’m not even wholly convinced there’s such a thing as a monosexual) – there’s a continuous multi-dimensional space in which everyone lies, and we find it operationally useful to have words that describe where we are relative to some of the boundary points in that space that almost nobody experiences perfectly.

There are as many distinct experiences of being bisexual as there are bisexuals (though, as I keep finding out, being extremely confused and annoyed by this fact seems to be a pretty common experience for us), but it sure is difficult to have an “It’s Complicated” visibility day, and it seems surprisingly easy for people to forget we exist without regular reminders.

The approximation isn’t just useful for communicating infinite complexity in a finite amount of time, it’s useful because we build solidarity around those approximations.

(This is literally why I use the label bisexual incidentally. I’m much happier with just saying “It’s complicated and unlikely to impact your life either way and when it does I would be happy to give you a detailed explanation of my preferences” but that is less useful to both me and everyone else, so I no longer do)

Another truth/justice trade off in the LGBT space is “Born this way”. I am at this point confident of precisely two things about gender and sexuality:

  • They are probably the byproduct of some extremely complicated set of nature/nurture interactions like literally everything else in the human experience.
  • Anyone who currently expresses confidence that they know how those play out in practice might be right for the n=1 sample of themself (I am generally very skeptical of people’s claims that they understand what features are natural things they were born with and what are part of their upbringing. I present the entire feminist literature on privilege as evidence in defence of my skepticism, but I also don’t find it useful or polite to have arguments with people about their personal lived experiences), but are almost certainly wrong, or at least unsupported in their claim that this holds in generality.

I would be very surprised to learn that nobody was born this way, and I have an n=1 personal data point that there are bisexuals who would probably have been perfectly able to go through life considering themselves to be straight if they hadn’t noticed that other options were available. I think it likely that there’s a spectrum of variability in between, I just don’t know.

I think among ourselves most LGBT people are more than happy to admit that this stuff is complicated and we don’t understand it, but when confronted with people who just want us to be straight and cis and consider us deviants if we dare to differ on this point, born this way is very useful – it makes homophobia less a demand to conform to societal expectations (which would still be wrong, but is harder to convince people of) and more a call for genocide. The only way to stop LGBT being LGBT is to stop us existing, and that’s not what you mean, right?

(Historically there have been many cases where that was exactly what they meant, but these days it’s harder to get away with saying so even if you think it).

Even before the latest round of fake news we’ve had in the last couple of years, demanding perfect truth in politics seems like a great way to ensure that political change belongs to those less scrupulous than you. At the absolute minimum we need this sort of lies-to-normies to take complex issues and make them politically useful if we want the world to get better.

So: Truth or Justice?

To be honest, I still don’t know. My heart says truth, but my head says justice, which I’m almost certain is hilariously backwards and not how it’s supposed to work at all, but there you go. This is complicated, and maybe “Truth or Justice” is another of those labelling things that don’t really work for me. Hoisted by my own petard.

My suspicion though is that the world is a better place if not everyone is picking the exact same trade off – different people are differently placed for improving each, and it’s not all that useful to insist that someone inclined towards one should be strongly prioritising the other. It is useful to have both people for whom justice is their top priority, and people for whom truth is their top priority, and a world where we acknowledge only one point on the spectrum as valid is probably one that ends up with less truth and less justice than one where a wider variety is pursued. Monocultures just generally work less well in the long run, even by the standards of the monoculture.

Given that, it seems like a shame that right now most of the justice prioritising people seem to think the truth prioritising people are literally Hitler and vice versa.

(To be fair, the truth prioritising people probably think the justice prioritising people are figuratively Hitler).

Calls for “Why can’t we get along?” never go well, so I won’t make one here even though you could obviously ready into this article that that’s what I want even if I didn’t include this sentence as disclaimer, so instead I’ll end with a different call to action.

I wish we would all be better about acknowledging that this trade-off exists, and notice when we are making it, regardless of what we end up deciding about the people who have chosen a different trade-off.

If you’re justice-prioritising you might not feel able to do that in public because it would detract from your goals. That’s fine. Do it in private – with a couple close friends in the same sphere to start with. I’ve found people are generally much more receptive to it than you might think.

If you’re truth-prioritising, you have no excuse. Start talking about this in public more (some of you already are, I know). If what can be destroyed by the truth should be, there is no cost to acknowledging that the truth is sometimes harmful to others and that this is a trade-off you’re deliberately making.

Regardless of what we think the optimal trade-off between truth and justice is, I’m pretty sure a world that is better on both axes than the current one is possible. I’m significantly less sure that we’re on anything resembling a path to it, and I don’t know how to fix that, but I’d like to at least make sure we’re framing the problem correctly.

Python Coverage could be fast

Ned Batchelder’s coverage.py is a foundation of the Python testing ecosystem. It is solid, well maintained, and does its job extremely well. I think literally every Python project that cares about testing should be using it.

But it’s not without its faults. Specifically, its performance can be quite bad. On some workloads it’s absolutely fine, but on others you can see anything up to an order of magnitude slow down (and this is just on CPython. On pypy it can be even worse).

Recently, after some rather questionable late night hacking (and a significant amount of fixing not late at night), I finally made good on my promise that Hypothesis would eventually use coverage information and shipped Hypothesis 3.29.0 which added a dependency on Coverage and turned it on for every Hypothesis based test.

This hasn’t been an entirely smooth process – some for reasons that are my fault, and some that users are now running into these performance problems.

The right place to fix this is obviously in Coverage rather than Hypothesis itself, so I’ve been looking into this recently. I’ve already made one patch which gives branch coverage a 50% speedup in a loop-based microbenchmark and about a 20% speedup on one real world example I tried it on.

The idea of the patch is very straightforward (though apparently I’m a unusual in thinking that “Here I wrote you a hash table!!!” is a straightforward patch). Coverage creates a lot of Python objects in a very hot part of the code, so this caches them off an integer key so that most of the time it can omit creating those objects and significantly speed things up as a result.

Unfortunately that’s probably it for now. My priorities for the immediate future are PhD, paid work, and conference prep, which means that I certainly don’t have any time in the next month and probably not the next couple of months (this could be fixed by making this paid work. I may do a kickstarter or something for that, but in the meantime if any interested companies wanted to fund this work I’d be more than happy to discuss it…).

So I thought I’d write down my notes before I forget. These are both for future-me and for anyone interested who feels motivated to work on this problem in the meantime.

Initial Benchmarking

I haven’t done super formal benchmarking, but I set up pytest-benchmark with some basic benchmarks that just ran a loop adding numbers.

The benchmarking functionality itself was pretty great but I didn’t find it easy to compare benchmarks in the way that I wanted – in particular I had the same benchmark which was run in three different ways (no coverage, line coverage, branch coverage) and I wanted to break those down for side-by-side comparison, but I couldn’t find any functionality to do so (I admit I didn’t look very hard). It was nice having the statistics handled though and I will almost certainly want to sink some time into getting a decent pytest-benchmark suite for coverage if I work on this further.

Real World Benchmarking

The real world benchmark I used was Alex Groce’s tstl, because his usage profile is similar to mine (there’s a lot of overlap between what Hypothesis and TSTL do), and he had an existing example that was seeing an order of magnitude slow down. This is the example that gets a 20% speedup from my above patch.

The problem can be reproduced as follows:

git clone https://github.com/agroce/tstl.git
cd tstl
virtualenv v
source v/bin/activate
pip install .
cd examples/AVL
tstl avlnodisp.tstl
tstl_rt --seed=0 --timeout=30 
tstl_rt --seed=0 --timeout=30 --noCover

The thing to compare is the total number of test operations run in the outputs from each of the test_rt commands. For me I see “12192 TOTAL TEST OPERATIONS” with coverage, and “96938 TOTAL TEST OPERATIONS” without, so it runs about 8 times as many operations in the same time frame with coverage turned off (this is without my patch. With my patch I get 14665 under coverage, so about 20% more).

Profiling Coverage

I confess I didn’t figure out how to profile coverage until after I made the above patch. I had a benchmark I was measuring, and just based on inspection I was more than 90% certain that the above would help, so I decided to just give it a go and validate my suspicion and turned out to be right.

But after I’d picked the most obvious low hanging fruit I figured it would be silly to try to proceed further without getting profiling set up, so I poked around. I spent a little time trying to get google-perf-tools working with Python and failing, but eventually figured out that I could do it with perf and it works great (modulo quite a lot of hacking and data munging).

The basic idea with perf is that you run your program under “perf record” and it gives you raw output data. You can then do analysis on this to find out about your program’s performance.

The first thing to do to use perf is that you need to make sure that everything is compiled with debug symbols. This includes both your extension and Python itself.

To get a Python with debug symbols I used pyenv‘s python-build plugin:

export PYTHON_CFLAGS='-pg'
~/.pyenv/plugins/python-build/bin/python-build 2.7.13 ~/debug-python2

This builds a version of Python 2 (TSTL doesn’t work under Python 3) with the “-pg” flag to gcc which includes debug symbols. I also modified setup.py for coverage to include  extra_compile_args=[‘-pg’] (it should be possible to do this with an environment variable, but I didn’t try).

Once I had that, running under perf was straightforward:

perf record tstl_rt --seed=0 --timeout=30

This creates a file called perf.data that you can analyze. I did not find prof report, the default way of analyzing it, super helpful, so I used CPU Flame Graphs.

I was only interested in the performance for calls below CTracer_trace, and I didn’t find the way it was spread out in the SVG (there were a lot of bits) very helpful, so I ended up aggregating the data through some um very sophisticated data analysis tools as follows:

perf script > out.perf && \
    ~/scratch/FlameGraph/stackcollapse-perf.pl out.perf | \
    grep CTracer | sed 's/.\+;CTracer_trace/CTracer_trace/' | \
    sort | \
    python sum.py > out2.folded
~/scratch/FlameGraph/flamegraph.pl out2.folded > out.svg

sum.py is the following very basic code:

from __future__ import print_function

import sys

if __name__ == '__main__':
        prev = None
        for l in sys.stdin:
                u, v = l.split()
                v = int(v)
                if prev is None:
                        prev = u
                        count = v
                elif prev == u:
                        count += v
                else:
                        print(prev, count)
                        prev = u
                        count = v
        print(prev, count)

(the data munging earlier creates duplicated entries, so this merges them together).

WordPress won’t let me upload the generated SVG “For Security Reasons” (that do not apparently preclude running WordPress itself), so here’s a gist of it, and her’es one from before my patch was applied (right click and view image in a new tab to get a usable interactive version of it)

pypy

PyPy performance for coverage is more complicated. My understanding is that there are roughly three classes of problems here:

  1. coverage itself is not as well optimised as it could be (same problem as CPython)
  2. Using settrace interferes with the JIT
  3. The baseline speed of pypy operations is much faster so coverage is a much higher overhead by comparison.

The first is the only one I could deal with, and I think it probably will benefit significantly from whatever changes I make to the C extension also being ported over to the pure Python version (pypy doesn’t use the C extension tracer because it’s even slower than the pure python one on pypy), but I’m not sure that will be enough – I suspect there are also going to be more changes to pypy internals required for this, and I don’t know enough about those to say how difficult or easy they are.

The Limits of What Is Possible

Python coverage is never going to run at the speed of Python without coverage, especially on pypy.

You can see the limits of how much faster it could be by running with an empty trace function (note: Whether you are using a C or Python level trace function makes a big difference. sys.settrace is ruinously slow even with an empty function).

The difference varies significantly depending on your code though – with the TSTL workload above I see a 50% slow down with an empty C level trace function. With more microbenchmark style workloads with few functions and lots of looping I see almost no speed loss.

So my suspicion is that for CPython at least we can get coverage to reliably be within a factor of two of running without it, and maybe reliably within a factor of 1.5.

What next

For now my plan is to shepherd the patch from the beginning of this post and otherwise ignore this problem for the next couple of months.

Based on the profiling I did above most of the time is currently being spent in PyDict_SetItem, so I think the obvious next line of attack when I do start working on this is to replace the file_data objects in coverage which currently use Python dictionaries keyed off Python values with some sort of specialized data structure (possibly another hash table, possibly something better optimized for write heavy workloads). Longer term I think the goal should be move all calls back into Python land out of the trace function and just normalize at the end of tracing.

Even the more modest goal is a bit more invasive of a change than I wanted to start with, hence the above rather more conservative patch, but there’s nothing conceptually difficult to it – it just involves a bunch of slog and basic engineering work followed by some experimenting with clever data structure designs.

Once I’ve made it through the next month or two I’ll start seeing about getting some work on this funded. I’ve already suggested the notion to an existing customer who I know is having problems with coverage performance, but if they don’t want to fund it (which would be totally understandable) I’ll look further afield.

My fall back plan is a Kickstarter for this, but honestly I think some motivated company who is suffering from this should just think about picking up the tab.

I’ve been doing a bunch of funded work on Hypothesis for Stripe and Smarkets (here and here so far, with more to come) and it’s been going great – it’s worked out well for me, them, and Hypothesis users at large, and I don’t see why other projects shouldn’t benefit from the same (I’d encourage paying people who are actually maintainers of those projects by default, but many of them including Ned have full time jobs and I’m more flexibly available).

We’re not talking about a lot of money – a couple of weeks of development work (and, say, a 10-20% extra consultancy fee for Ned) should be enough to see some serious performance improvements, and as well as making your developers much happier, you’ll also earn some serious community good will (which is great when it comes to hiring new developers). That’s probably less than a month of your normal meeting schedule costs you.

This is a problem that affects a large majority of people who care about testing Python, which should include most commercial Python users, so if that’s you why not get in touch?

This entry was posted in Python on by .