Why is the list of dicts in a `Context` maintained in reverse order?

Django contexts maintain a stack of dicts used for looking things up in the context, but this stack is maintained in what appears to be the reverse of the optimal order. Excerpts from django.template.BaseContext:

    def __iter__(self):
        return reversed(self.dicts)

    def push(self, *args, **kwargs):
        dicts = []
        for d in args:
            if isinstance(d, BaseContext):
                dicts += d.dicts[1:]
        return ContextDict(self, *dicts, **kwargs)

    def __getitem__(self, key):
        "Get a variable's value, starting at the current context and going upward"
        for d in reversed(self.dicts):
            if key in d:
                return d[key]
        raise KeyError(key)

    def get(self, key, otherwise=None):
        for d in reversed(self.dicts):
            if key in d:
                return d[key]
        return otherwise

Note the pervasive use of reversed in the above. Given that lookup operations (get and __getitem__) should be as quick as possible, why not keep the dicts list in the reverse order to currently, so that the reversed operations can be avoided? Is there some other frequent operation which benefits from the dicts being in the current order? I realise that reversed just returns an iterator and is not making a copy of the list, but still, I’m curious as to why it’s done this way.

Good question, seems like the code optimizes for pushing/popping the stack – whether that would be useful I cannot say (I agree with you that get/__getitem__ is probably more important). So assuming this was optimizing for pushing/popping (ie dicts.append is O(1) vs dicts.insert(0, ...) is O(n) and same for .pop() vs .pop(0)) we might be able to use a collections.deque instead to have both fast (assuming the O(n) would even be a problem)?

I guess having a somewhat realworld templating benchmark would help :slight_smile: Out of curiosity though, how did you stumble over that?

I was looking at a use case for Web components in Django using the Slippers library where it didn’t do what I needed it to, and investigating how I could make it meet my requirements led me to this part of the Django internals.

I guess Django templates are fast enough for most people most of the time - fair enough. I just asked the question out of curiosity :smile:

Oh, Slippers looks interesting.

Sorry, I didn’t want to leave that impression! By all means if we can make it faster let’s do it. To be honest that code has probably been like this since 2010 and before… So if there have been reasons to write it that way we simply might not remember them anymore. In the end Django has a relatively good test coverage, so we should be able to get rid of the reversing assuming we find some reasonable indicator for a performance improvement.

P.S.: FWIW the DTL is quite slow :wink:

1 Like

I would like to see some optimization of the DTL. Eliminating all those reversed() calls could be a nice little micro-optimization. I’m sure there are others.

Now that there’s no need for Python 2.x support, use of 3.x-specific improvements (like collections.ChainMap) are worth thinking about.

Yes maybe. Worth checking Trac to see if anyone has proposed that one before, in case it isn’t feasible.