Opened 6 years ago

Closed 6 years ago

Last modified 5 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: UI/UX:

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 6 years ago.
13812_faster_context_using_deque.diff (2.6 KB) - added by Satoru Logic 6 years ago.

Download all attachments as: .zip

Change History (12)

Changed 6 years ago by Satoru Logic

Attachment: 13812_faster_context.diff added

comment:1 Changed 6 years ago by Alex Gaynor

Needs documentation: unset
Needs tests: unset
Patch needs improvement: unset

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 Changed 6 years ago by 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.

comment:3 Changed 6 years ago by 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.

Changed 6 years ago by Satoru Logic

comment:4 in reply to:  1 Changed 6 years ago by Satoru Logic

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 Changed 6 years ago by Satoru Logic

Owner: changed from nobody to Satoru Logic

comment:6 Changed 6 years ago by Satoru Logic

Cc: satorulogic@… added

comment:7 Changed 6 years ago by Łukasz Rekucki

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

comment:8 Changed 6 years ago by Ł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.

comment:9 Changed 6 years ago by Alex Gaynor

Resolution: fixed
Status: newclosed

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

comment:10 Changed 5 years ago by Jacob

milestone: 1.3

Milestone 1.3 deleted

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