Velocity Reviews > Optimising literals away

# Optimising literals away

Tobias Weber
Guest
Posts: n/a

 08-30-2010
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

Thomas Jollans
Guest
Posts: n/a

 08-30-2010
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
>>>

Benjamin Peterson
Guest
Posts: n/a

 08-30-2010
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.

Arnaud Delobelle
Guest
Posts: n/a

 08-30-2010
Tobias Weber <(E-Mail Removed)> 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

Aleksey
Guest
Posts: n/a

 08-31-2010
On Aug 30, 10:38*pm, Tobias Weber <(E-Mail Removed)> 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/xpy...kBook/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
Guest
Posts: n/a

 08-31-2010
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

Stefan Behnel
Guest
Posts: n/a

 08-31-2010
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

Terry Reedy
Guest
Posts: n/a

 08-31-2010
On 8/31/2010 12:33 PM, Aleksey wrote:
> On Aug 30, 10:38 pm, Tobias Weber<(E-Mail Removed)> 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

MRAB
Guest
Posts: n/a

 08-31-2010
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<(E-Mail Removed)> 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.
>

Stefan Behnel
Guest
Posts: n/a

 09-01-2010
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