Opened 14 years ago

Closed 13 years ago

Last modified 12 years ago

#13812 closed (fixed)

[patch] Change the way BaseContext maintains the dicts

Reported by: Satoru Logic Owned by: Satoru Logic
Component: Template system Version: 1.2
Severity: Keywords: template context
Cc: Alex Gaynor, Fredde, satorulogic@… Triage Stage: Unreviewed
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: no UI/UX: no

Description

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.

Attachments (2)

13812_faster_context.diff (2.3 KB ) - added by Satoru Logic 14 years ago.
13812_faster_context_using_deque.diff (2.6 KB ) - added by Satoru Logic 14 years ago.

Download all attachments as: .zip

Change History (12)

by Satoru Logic, 14 years ago

Attachment: 13812_faster_context.diff added

comment:1 by Alex Gaynor, 14 years ago

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.

comment:2 by Fredde, 14 years ago

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.

comment:3 by Alex Gaynor, 14 years ago

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.

by Satoru Logic, 14 years ago

in reply to:  1 comment:4 by Satoru Logic, 14 years ago

Cc: Alex Gaynor Fredde added; Russell Keith-Magee removed

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.

comment:5 by Satoru Logic, 14 years ago

Owner: changed from nobody to Satoru Logic

comment:6 by Satoru Logic, 14 years ago

Cc: satorulogic@… added

comment:7 by Łukasz Rekucki, 14 years ago

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

comment:8 by Łukasz Rekucki, 14 years ago

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.

comment:9 by Alex Gaynor, 13 years ago

Resolution: fixed
Status: newclosed

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

comment:10 by Jacob, 12 years ago

milestone: 1.3

Milestone 1.3 deleted

Note: See TracTickets for help on using tickets.
Back to Top