Improved performance of django.template.base.Parser.

pop(0), which is used to fetch each token, is O(n) in the length of the
list. By reversing the list and operating off the end, we can perform
next_token(), prepend_token(), and delete_first_token() in constant
time.

1 files changed, 6 insertions, 4 deletions

diff --git a/django/template/base.py b/django/template/base.py
index 6e22fbdcca..7ee23f7ebf 100644
--- a/django/template/base.py
+++ b/django/template/base.py
@@ -405,7 +405,9 @@ class DebugLexer(Lexer):
 
 class Parser:
     def __init__(self, tokens, libraries=None, builtins=None, origin=None):
-        self.tokens = tokens
+        # Reverse the tokens so delete_first_token(), prepend_token(), and
+        # next_token() can operate at the end of the list in constant time.
+        self.tokens = list(reversed(tokens))
         self.tags = {}
         self.filters = {}
         self.command_stack = []
@@ -541,13 +543,13 @@ class Parser:
         raise self.error(token, msg)
 
     def next_token(self):
-        return self.tokens.pop(0)
+        return self.tokens.pop()
 
     def prepend_token(self, token):
-        self.tokens.insert(0, token)
+        self.tokens.append(token)
 
     def delete_first_token(self):
-        del self.tokens[0]
+        del self.tokens[-1]
 
     def add_library(self, lib):
         self.tags.update(lib.tags)