# Optimising literals away

Discussion in 'Python' started by Tobias Weber, Aug 30, 2010.

1. ### Tobias WeberGuest

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...

--
Tobias Weber

Tobias Weber, Aug 30, 2010

2. ### Thomas JollansGuest

On Monday 30 August 2010, it occurred to Tobias Weber to exclaim:
> 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:

>>> def m_l(arg):

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

.... if arg & set((1,2,3)):
.... return 4
....
>>> def m_s(arg):

.... if arg & {1, 2, 3}:
.... return 4
....
>>> from dis import dis
>>> dis(m_l)

15 BUILD_LIST 3
18 CALL_FUNCTION 1
21 BINARY_AND
22 POP_JUMP_IF_FALSE 29

28 RETURN_VALUE

32 RETURN_VALUE
>>> dis(m_t)

6 LOAD_CONST 5 ((1, 2, 3))
9 CALL_FUNCTION 1
12 BINARY_AND
13 POP_JUMP_IF_FALSE 20

19 RETURN_VALUE

23 RETURN_VALUE
>>> dis(m_s)

12 BUILD_SET 3
15 BINARY_AND
16 POP_JUMP_IF_FALSE 23

22 RETURN_VALUE

26 RETURN_VALUE
>>>

Thomas Jollans, Aug 30, 2010

3. ### Benjamin PetersonGuest

Tobias Weber <towb <at> gmx.net> writes:

>
> 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.

> 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.

Benjamin Peterson, Aug 30, 2010
4. ### Arnaud DelobelleGuest

Tobias Weber <> writes:

> 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...

>>> import dis
>>> def m(arg):

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

15 BUILD_LIST 3
18 CALL_FUNCTION 1
21 BINARY_AND
22 JUMP_IF_FALSE 5 (to 30)
25 POP_TOP

29 RETURN_VALUE
>> 30 POP_TOP

34 RETURN_VALUE

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

--
Arnaud

Arnaud Delobelle, Aug 30, 2010
5. ### AlekseyGuest

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.
>
> 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...
>
> --
>   Tobias Weber

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

Aleksey, Aug 31, 2010
6. ### John NagleGuest

On 8/30/2010 8:38 AM, Tobias Weber wrote:
> 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

John Nagle, Aug 31, 2010
7. ### Stefan BehnelGuest

John Nagle, 31.08.2010 21:03:
> On 8/30/2010 8:38 AM, Tobias Weber wrote:
>> 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".

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

Stefan Behnel, Aug 31, 2010
8. ### Terry ReedyGuest

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.

>> 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?

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.

--
Terry Jan Reedy

Terry Reedy, Aug 31, 2010
9. ### MRABGuest

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.

>>> 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?

>
> 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, Aug 31, 2010
10. ### Stefan BehnelGuest

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.

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

Stefan Behnel, Sep 1, 2010
11. ### Lie RyanGuest

On 09/01/10 17:06, Stefan Behnel wrote:
> 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.

> 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

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.

Lie Ryan, Sep 1, 2010
12. ### MRABGuest

On 01/09/2010 14:25, Lie Ryan wrote:
> On 09/01/10 17:06, Stefan Behnel wrote:
>> 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