Optimising literals away

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

  1. Tobias Weber

    Tobias Weber Guest

    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
    #1
    1. Advertising

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

    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
    >> 29 LOAD_CONST 0 (None)

    32 RETURN_VALUE
    >>> dis(m_t)

    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
    >> 20 LOAD_CONST 0 (None)

    23 RETURN_VALUE
    >>> dis(m_s)

    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
    >> 23 LOAD_CONST 0 (None)

    26 RETURN_VALUE
    >>>
    Thomas Jollans, Aug 30, 2010
    #2
    1. Advertising

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

    > 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.
    Benjamin Peterson, Aug 30, 2010
    #3
  4. 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...


    the dis module can help you for these:

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

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

    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
    >> 30 POP_TOP

    31 LOAD_CONST 0 (None)
    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
    #4
  5. Tobias Weber

    Aleksey Guest

    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
    #5
  6. Tobias Weber

    John Nagle Guest

    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
    #6
  7. 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
    #7
  8. Tobias Weber

    Terry Reedy Guest

    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
    #8
  9. Tobias Weber

    MRAB Guest

    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
    #9
  10. 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
    #10
  11. Tobias Weber

    Lie Ryan Guest

    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
    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.
    Lie Ryan, Sep 1, 2010
    #11
  12. Tobias Weber

    MRAB Guest

    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
    created, checked, and then discarded.
    MRAB, Sep 1, 2010
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MS

    Optimising a web app

    MS, Jun 24, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    441
    Sahil Malik
    Jun 27, 2004
  2. Jon Maz
    Replies:
    4
    Views:
    401
    Jon Maz
    May 27, 2004
  3. =?Utf-8?B?Q2hyaXMgUG9kbW9yZQ==?=

    Optimising pages for 640x480 or 800x600

    =?Utf-8?B?Q2hyaXMgUG9kbW9yZQ==?=, Dec 10, 2004, in forum: ASP .Net
    Replies:
    7
    Views:
    349
    =?Utf-8?B?Q2hyaXMgUG9kbW9yZQ==?=
    Dec 10, 2004
  4. BobLaughland

    Optimising a web page

    BobLaughland, Mar 7, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    342
    =?Utf-8?B?RFdT?=
    Mar 7, 2006
  5. John Goche
    Replies:
    8
    Views:
    16,448
Loading...

Share This Page