Optimising literals away

[Tobias Weber]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

def m(arg):
if arg & set([1,2,3]):
return 4

Is the set created every time the method is called? What about a
frozenset? Or tuple vs list? After how many calls per second does it pay
to save it at the module level? Would anybody else find this ugly?

Also I never profiled the regular expression cache...

 

[Thomas Jollans]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

def m(arg):
if arg & set([1,2,3]):
return 4

Is the set created every time the method is called? What about a
frozenset? Or tuple vs list? After how many calls per second does it pay
to save it at the module level? Would anybody else find this ugly?

That creates a list, and then calls "set" with the list as an argument. Every
time, because that's what the code says: call "set" with a new list containing
1, 2, and 3.

If you use a tuple instead of the list, the tuple can be loaded as a whole --
as tuples are immutable, it doesn't have to be re-created every time, it can
be the same object.

If you use a set literal instead of calling "set", the set is constructed
directly, like a list would be.

Details:
.... if arg & set([1,2,3]):
.... return 4
.... .... if arg & set((1,2,3)):
.... return 4
.... .... if arg & {1, 2, 3}:
.... return 4
.... 2 0 LOAD_FAST 0 (arg)
3 LOAD_GLOBAL 0 (set)
6 LOAD_CONST 1 (1)
9 LOAD_CONST 2 (2)
12 LOAD_CONST 3 (3)
15 BUILD_LIST 3
18 CALL_FUNCTION 1
21 BINARY_AND
22 POP_JUMP_IF_FALSE 29

3 25 LOAD_CONST 4 (4)
28 RETURN_VALUE 2 0 LOAD_FAST 0 (arg)
3 LOAD_GLOBAL 0 (set)
6 LOAD_CONST 5 ((1, 2, 3))
9 CALL_FUNCTION 1
12 BINARY_AND
13 POP_JUMP_IF_FALSE 20

3 16 LOAD_CONST 4 (4)
19 RETURN_VALUE 2 0 LOAD_FAST 0 (arg)
3 LOAD_CONST 1 (1)
6 LOAD_CONST 2 (2)
9 LOAD_CONST 3 (3)
12 BUILD_SET 3
15 BINARY_AND
16 POP_JUMP_IF_FALSE 23

3 19 LOAD_CONST 4 (4)
22 RETURN_VALUE

 

[Benjamin Peterson]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

def m(arg):
if arg & set([1,2,3]):
return 4

Is the set created every time the method is called?

Yes, and the list.

What about a
frozenset?
Yep.

Or tuple vs list?

Tuples containing other immutable literals can be optimized. (In cpython anyway.)

After how many calls per second does it pay
to save it at the module level?

Ask the profiler. Probably not many.

Would anybody else find this ugly?

I do it all the time.

 

[Arnaud Delobelle]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

def m(arg):
if arg & set([1,2,3]):
return 4

Is the set created every time the method is called? What about a
frozenset? Or tuple vs list? After how many calls per second does it pay
to save it at the module level? Would anybody else find this ugly?

Also I never profiled the regular expression cache...

the dis module can help you for these:
.... if arg & set([1,2,3]):
.... return 4
.... 2 0 LOAD_FAST 0 (arg)
3 LOAD_GLOBAL 0 (set)
6 LOAD_CONST 1 (1)
9 LOAD_CONST 2 (2)
12 LOAD_CONST 3 (3)
15 BUILD_LIST 3
18 CALL_FUNCTION 1
21 BINARY_AND
22 JUMP_IF_FALSE 5 (to 30)
25 POP_TOP

3 26 LOAD_CONST 4 (4)
29 RETURN_VALUE 31 LOAD_CONST 0 (None)
34 RETURN_VALUE

As you can see, the list literal is built every time the function code
is executed.

 

[Aleksey]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

def m(arg):
  if arg & set([1,2,3]):
    return 4

Is the set created every time the method is called? What about a
frozenset? Or tuple vs list? After how many calls per second does it pay
to save it at the module level? Would anybody else find this ugly?

Also I never profiled the regular expression cache...

I test time creation of any types ang get next result:

dictionary = 393 000 * 10
frozenset = 267 000 * 10
list = 519 000 * 10
set = 268 000 * 10
tuple = 5 935 500 * 10
global assign = 5 882 700 * 10

All results multiple by 10 becouse i do 10 creations in one loop and
count loops per second.

As you see create global variable is more faster (20 times) then
create list and from it create set! Assigments is ~ 5 882 000*10,>>>
set creation is 268 000*10

My test system is Ubuntu 10.04, Dell Inspiron 1525, Core2Duo, T8300,
2Gb , Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56) [GCC 4.4.3].
I make tests with XPyLIB.timetest module. (XPyLIB hosted at
sourceforge - http://sourceforge.net/apps/trac/xpylib/wiki/CookBook/TimeTest)

Assign global (pre declared by "global") function is next (N - is a
times of repeating):

gset = set((1,2,3))
def t_set_assign_global(ntimes = N, funcloop=u'funcloop',
excludecall=u'excludecall'):
"""Set assigment from global : global=(1,2,3); loop a = global 10
times in while.

@UID@ e710b888-bacd-4248-9ff7-1f7a348e1c8f
@author@ Mazhugin Aleksey
@score_common@ 1
"""
a = 0
global gset
while ntimes > 0:
a = gset
a = gset
a = gset
a = gset
a = gset
a = gset
a = gset
a = gset
a = gset
a = gset
ntimes -= 1



Set function is next:

def t_set_create(ntimes = N, funcloop=u'funcloop',
excludecall=u'excludecall'):
"""Set creation : t=(1,2,3); loop a = set(t) 10 times in while.

@UID@ a021a756-f9a5-44ec-b9e6-e5532b56c09f
@author@ Mazhugin Aleksey
@score_common@ 1
"""
a = 0
t = (1,2,3)
while ntimes > 0:
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
a = set(t)
ntimes -= 1



Also i test regular expression compiled pattern vs non-compiled:

compiled = 343 000*2
not compiled = 164 000*2

Functions is next:

patt5 = u'*.tmp,*.pyc,*.pyo,*.bak,*.log'
path1 = u'/home/user/project/src/file.ext'
path2 = u'/home/user/project/logs/debug.log'

def t_rematch(ntimes=10, funcloop=u'funcloop',
excludecall='excludecall'):
"""
Compiled.

@UID@ 665f4014-9c11-4668-baae-e49230027bd4
@author@ Mazhugin Aleksey
@score_common@ 1
"""
ci = patt5.replace(u'\\',u'\\\\').replace(u'|',u'\
\|').replace(u'.',u'\\.').replace(u'*',u'.*'). \
replace(u'?',u'.?').replace(u'$',u'\\$').replace(u'^',u'\
\^').replace(u'{',u'\\{'). \
replace(u'(',u'\\(').replace(u'[',u'\\[').replace(u'+',u'\\
+').split(u',')
repat = u'|'.join([u'('+i+u'$)' for i in ci])
rec = re.compile(repat)
r = 0
while ntimes:
r = rec.match(path1) is not None
r = rec.match(path2) is not None
ntimes -= 1

def t_rematch_string(ntimes=10, funcloop=u'funcloop',
excludecall='excludecall'):
"""
Not compiled.

@UID@ 80fa1ca3-5d51-4f6e-8ac2-4ccafe4c1160
@author@ Mazhugin Aleksey
@score_common@ 1
"""
ci = patt5.replace(u'\\',u'\\\\').replace(u'|',u'\
\|').replace(u'.',u'\\.').replace(u'*',u'.*'). \
replace(u'?',u'.?').replace(u'$',u'\\$').replace(u'^',u'\
\^').replace(u'{',u'\\{'). \
replace(u'(',u'\\(').replace(u'[',u'\\[').replace(u'+',u'\\
+').split(u',')
repat = u'|'.join([u'('+i+u'$)' for i in ci])
#rec = re.compile(repat)
r = 0
while ntimes:
r = re.match(repat, path1) is not None
r = re.match(repat, path2) is not None
ntimes -= 1

 

[John Nagle]

Hi,
whenever I type an "object literal" I'm unsure what optimisation will do
to it.

CPython is a "naive interpreter". It has almost no optimization.
It doesn't even really comprehend "constants".
This is an implementation problem, not a language problem.

Shed Skin has serious optimization but limits the language.
PyPy has been trying for years, but it still barely works.
Iron Python seems to be nearing end of life, as Microsoft
phases it out. Unladen Swallow seems to be in trouble; it's
been almost a year since the last "quarterly release".

John Nagle

 

[Stefan Behnel]

John Nagle, 31.08.2010 21:03:

CPython is a "naive interpreter". It has almost no optimization.
It doesn't even really comprehend "constants".
This is an implementation problem, not a language problem.

Shed Skin has serious optimization but limits the language.
PyPy has been trying for years, but it still barely works.
Iron Python seems to be nearing end of life, as Microsoft
phases it out. Unladen Swallow seems to be in trouble; it's
been almost a year since the last "quarterly release".

To continue the list, Cython also has a couple of optimisations for
literals. It caches simple immutable constants, applies numeric constant
folding and it's obviously a lot faster in packing tuples and lists than
CPython as it avoids the interpreter loop. It also optimises away the
literal sequences in "in" tests such as

if x in (1,2,3):
...

which, in the best case of integer literals, even compile down into C
switch statements.

Stefan

 

[Terry Reedy]

Optimizations are generally implentation dependent. CPython currently
creates numbers, strings, and tuple literals just once. Mutable literals
must be created each time as they may be bound and saved.

def m(arg):
if arg& set([1,2,3]):

set() is a function call, not a literal. When m is called, who knows
what 'set' will be bound to? In Py3, at least, you could write {1,2,3},
which is much faster as it avoids creating and deleting a list. On my
machine, .35 versus .88 usec. Even then, it must be calculated each time
because sets are mutable and could be returned to the calling code.

Defining module level constants is considered good practice in some
circles, especially if is something you might want to change. That is
what function definitions are (as long as the name is not redefined.
This is different from having lots of module level variables.

To see what CPython does, you can use the dis module.

 

[MRAB]

Optimizations are generally implentation dependent. CPython currently
creates numbers, strings, and tuple literals just once. Mutable literals
must be created each time as they may be bound and saved.

def m(arg):
if arg& set([1,2,3]):

set() is a function call, not a literal. When m is called, who knows
what 'set' will be bound to? In Py3, at least, you could write {1,2,3},
which is much faster as it avoids creating and deleting a list. On my
machine, .35 versus .88 usec. Even then, it must be calculated each time
because sets are mutable and could be returned to the calling code.

There's still the possibility of some optimisation. If the resulting
set is never stored anywhere (bound to a name, for example) then it
could be created once. When the expression is evaluated there could be
a check so see whether 'set' is bound to the built-in class, and, if it
is, then just use the pre-created set.

 

[Stefan Behnel]

MRAB, 31.08.2010 23:53:

On Aug 30, 10:38 pm, Tobias Weber wrote:
Hi,
whenever I type an "object literal" I'm unsure what optimisation
will do
to it.

Optimizations are generally implentation dependent. CPython currently
creates numbers, strings, and tuple literals just once. Mutable literals
must be created each time as they may be bound and saved.

def m(arg):
if arg& set([1,2,3]):

set() is a function call, not a literal. When m is called, who knows
what 'set' will be bound to? In Py3, at least, you could write {1,2,3},
which is much faster as it avoids creating and deleting a list. On my
machine, .35 versus .88 usec. Even then, it must be calculated each time
because sets are mutable and could be returned to the calling code.

There's still the possibility of some optimisation. If the resulting
set is never stored anywhere (bound to a name, for example) then it
could be created once. When the expression is evaluated there could be
a check so see whether 'set' is bound to the built-in class, and, if it
is, then just use the pre-created set.

Cython applies this kind of optimistic optimisation in a couple of other
cases and I can affirm that it often makes sense to do that. However,
drawback here: the set takes up space while not being used (not a huge
problem if literals are expected to be small), and the global lookup of
"set" still has to be done to determine if it *is* the builtin set type.
After that, however, the savings should be considerable.

Another possibility: always cache the set and create a copy on access.
Copying a set avoids the entire eval loop overhead and runs in a C loop
instead, using cached item instances with (most likely) cached hash values.
So even that will most likely be much faster than the spelled-out code above.

Stefan

 

[Lie Ryan]

MRAB, 31.08.2010 23:53:

On 8/31/2010 12:33 PM, Aleksey wrote:
On Aug 30, 10:38 pm, Tobias Weber wrote:
Hi,
whenever I type an "object literal" I'm unsure what optimisation
will do
to it.

Optimizations are generally implentation dependent. CPython currently
creates numbers, strings, and tuple literals just once. Mutable literals
must be created each time as they may be bound and saved.

def m(arg):
if arg& set([1,2,3]):

set() is a function call, not a literal. When m is called, who knows
what 'set' will be bound to? In Py3, at least, you could write {1,2,3},
which is much faster as it avoids creating and deleting a list. On my
machine, .35 versus .88 usec. Even then, it must be calculated each time
because sets are mutable and could be returned to the calling code.

There's still the possibility of some optimisation. If the resulting
set is never stored anywhere (bound to a name, for example) then it
could be created once. When the expression is evaluated there could be
a check so see whether 'set' is bound to the built-in class, and, if it
is, then just use the pre-created set.

What if the set is mutated by the function? That will modify the global
cache of the set; one way to prevent mutation is to use frozenset, but
from the back of my mind, I think there was a discussion that rejects
set literals producing a frozen set instead of regular set.

Cython applies this kind of optimistic optimisation in a couple of other
cases and I can affirm that it often makes sense to do that. However,
drawback here: the set takes up space while not being used (not a huge
problem if literals are expected to be small), and the global lookup of
"set" still has to be done to determine if it *is* the builtin set type.
After that, however, the savings should be considerable.

Another possibility: always cache the set and create a copy on access.
Copying a set avoids the entire eval loop overhead and runs in a C loop
instead, using cached item instances with (most likely) cached hash
values. So even that will most likely be much faster than the
spelled-out code above.

I think that these kind of optimizations would probably be
out-of-character for CPython, which values implementation simplicity
above small increase in speed. Sets are not that much used and
optimizing this particular case seems to be prone to create many subtle
issues (especially with multithreading).

In other word, these optimizations makes sense for Python
implementations that are heavily geared for speed (e.g. Unladen Swallow,
Stackless Python, PyPy[1], Cython); but probably may only have a
minuscule chance of being implemented in CPython.

[1] yes, their goal was to be faster than CPython (and faster than the
speed of photon in vacuum), though AFAICT they have yet to succeed.

 

[MRAB]

MRAB, 31.08.2010 23:53:

On 31/08/2010 21:18, Terry Reedy wrote:
On 8/31/2010 12:33 PM, Aleksey wrote:
On Aug 30, 10:38 pm, Tobias Weber wrote:
Hi,
whenever I type an "object literal" I'm unsure what optimisation
will do
to it.

Optimizations are generally implentation dependent. CPython currently
creates numbers, strings, and tuple literals just once. Mutable literals
must be created each time as they may be bound and saved.

def m(arg):
if arg& set([1,2,3]):

set() is a function call, not a literal. When m is called, who knows
what 'set' will be bound to? In Py3, at least, you could write {1,2,3},
which is much faster as it avoids creating and deleting a list. On my
machine, .35 versus .88 usec. Even then, it must be calculated each time
because sets are mutable and could be returned to the calling code.

There's still the possibility of some optimisation. If the resulting
set is never stored anywhere (bound to a name, for example) then it
could be created once. When the expression is evaluated there could be
a check so see whether 'set' is bound to the built-in class, and, if it
is, then just use the pre-created set.

What if the set is mutated by the function? That will modify the global
cache of the set; one way to prevent mutation is to use frozenset, but
from the back of my mind, I think there was a discussion that rejects
set literals producing a frozen set instead of regular set.

[snip]
I was talking about a use case like the example code, where the set is
created, checked, and then discarded.