[patch] Change the way BaseContext maintains the dicts

[Satoru Logic]

In django.template.context, BaseContext is the base class of several context classes.

By maintaining a list of dict, it supports a LIFO way of resolving template variables with contexts.

In the __getitem__ method, it searches for a dict reversely using reversed, I think I can make it a little faster by just iterating the dict list, and maintain the reversed list in push.

[Alex Gaynor]

Maintaing the list this way is an order of magnitude more expensive, both pop(0) and insert(0) are O(n) operations, whereas using reversed() is the same complexity.

[Fredde]

Can collections.deque (​http://docs.python.org/library/collections.html#deque-objects) be an alternative if this is critical for djangos performance?

It was added in python 2.4, which is the minimum requirement for django 1.2 if I don't remember wrong.

[Alex Gaynor]

I'm not sure I follow what the issue with using reversed is? But yes, a deque could be used as it would give us O(1) insert/pop.

[Satoru Logic]

Replying to Alex:

Maintaing the list this way is an order of magnitude more expensive, both pop(0) and insert(0) are O(n) operations, whereas using reversed() is the same complexity.

You are right :)

I didn't realized that insert(0, val) and pop(0) were O(n) operations and thought of a python list as a traditional linked list in which insert(0, val) and pop(0) were O(1) operations.

After reading ​http://www.python.org/dev/peps/pep-0290/#inserting-and-popping-at-the-beginning-of-lists, now I know that the right way to make it faster is to use collections.deque.

[Łukasz Rekucki]

Actually, looping with deque seems to be much slower: ​http://ideone.com/1SzEm, but you should probably do a real benchmark first.

[Łukasz Rekucki]

Nevermind, my mistake. It turns out that call to reversed() is the most expensive part of the loop (which I omitted by accident in the first test case). Anyway, a real benchmark is probably a good idea.

[Alex Gaynor]

This was fixed as a result of the work that brought us template compilation.

[Jacob]

Milestone 1.3 deleted