Code

Opened 4 years ago

Closed 4 years ago

Last modified 3 years ago

#13812 closed (fixed)

[patch] Change the way BaseContext maintains the dicts

Reported by: suzaku Owned by: suzaku
Component: Template system Version: 1.2
Severity: Keywords: template context
Cc: Alex, 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 suzaku 4 years ago.
13812_faster_context_using_deque.diff (2.6 KB) - added by suzaku 4 years ago.

Download all attachments as: .zip

Change History (12)

Changed 4 years ago by suzaku

comment:1 follow-up: Changed 4 years ago by Alex

  • 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 4 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 4 years ago by Alex

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 4 years ago by suzaku

comment:4 in reply to: ↑ 1 Changed 4 years ago by suzaku

  • Cc Alex, Fredde added; russellm 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 4 years ago by suzaku

  • Owner changed from nobody to suzaku

comment:6 Changed 4 years ago by suzaku

  • Cc satorulogic@… added

comment:7 Changed 4 years ago by lrekucki

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 4 years ago by lrekucki

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 4 years ago by Alex

  • Resolution set to fixed
  • Status changed from new to closed

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

comment:10 Changed 3 years ago by jacob

  • milestone 1.3 deleted

Milestone 1.3 deleted

Add Comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
as The resolution will be set. Next status will be 'closed'
The resolution will be deleted. Next status will be 'new'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.