Description

serhiy-storchaka

opened on Dec 15, 2017

Issue body actions

BPO	32338
Nosy	@rhettinger, @vstinner, @ezio-melotti, @methane, @serhiy-storchaka, @miss-islington
PRs	bpo-32338: OrderedDict import is no longer needed in re. #4891 bpo-32360: Remove OrderedDict from re module #5013 [3.7] bpo-32338: OrderedDict import is no longer needed in re. (GH-4891) #6073

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2018-03-11.07:06:10.801>
created_at = <Date 2017-12-15.18:21:39.079>
labels = ['expert-regex', 'type-feature', 'library', '3.7']
title = 'Save OrderedDict import in re'
updated_at = <Date 2018-03-11.07:06:10.799>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2018-03-11.07:06:10.799>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2018-03-11.07:06:10.801>
closer = 'serhiy.storchaka'
components = ['Library (Lib)', 'Regular Expressions']
creation = <Date 2017-12-15.18:21:39.079>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 32338
keywords = ['patch']
message_count = 10.0
messages = ['308418', '308516', '308524', '308525', '308526', '308527', '308529', '308534', '313583', '313584']
nosy_count = 7.0
nosy_names = ['rhettinger', 'vstinner', 'ezio.melotti', 'mrabarnett', 'methane', 'serhiy.storchaka', 'miss-islington']
pr_nums = ['4891', '5013', '6073']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue32338'
versions = ['Python 3.7']

Activity

1. serhiy-storchaka commented on Dec 15, 2017

   

   serhiy-storchaka

   on Dec 15, 2017

   MemberAuthor

   More actions

   Since regular dicts are now ordered by default, the OrderedDict import is no longer necessary.
2. serhiy-storchaka

   added

   3.7 (EOL)end of lifeend of life

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   topic-regex

   type-featureA feature request or enhancementA feature request or enhancement

   on Dec 15, 2017
3. methane commented on Dec 18, 2017

   

   methane

   on Dec 18, 2017

   Member

   More actions

   Please don't do this.
   del d[next(iter(d))] is not O(1) on current dict implementation.
   OrderedDict is designed for such use cases. Please keep using it.
4. serhiy-storchaka commented on Dec 18, 2017

   

   serhiy-storchaka

   on Dec 18, 2017

   MemberAuthor

   More actions

   This is surprising. But OrderedDict also can be O(N) here.

   Do you have benchmarking results Inada?
5. methane commented on Dec 18, 2017

   

   methane

   on Dec 18, 2017

   Member

   More actions

   This is surprising. But OrderedDict also can be O(N) here.

   Current dict implementation doesn't skip empty entries.
   So next(iter(D)) takes time.
   On the other hand, OrderedDict uses doubly-linked list to find first entry.

   (I fixed it in compact ODict branch, but it added one word to dict)

   Do you have benchmarking results Inada?

   $ ./python -m perf timeit -s 'cache={}' -- '
   for i in range(10000):
       if len(cache) > 512:
           del cache[next(iter(cache))]
       cache[i]=i
   '
   .....................
   Mean +- std dev: 6.81 ms +- 0.08 ms
   
   $ ./python -m perf timeit -s 'from collections import OrderedDict; cache=OrderedDict()' -- '
   for i in range(10000):
       if len(cache) > 512:
           cache.popitem(last=False)
       cache[i]=i
   '
   .....................
   Mean +- std dev: 3.75 ms +- 0.07 ms

   Performance difference is measurable even when N is only 512.

   Maybe, we can use hack similar to Python 3.5 had for O(1) popitem().
   When entries[0].key==NULL, (Py_ssize_t)entries[0].value can be index
   to first known non-empty entry.
6. methane commented on Dec 18, 2017

   

   methane

   on Dec 18, 2017

   Member

   More actions

   Hmm, 0.3 μs for each lookup may be negligible compared to re.compile() speed?
7. vstinner commented on Dec 18, 2017

   

   vstinner

   on Dec 18, 2017

   Member

   More actions

   del d[next(iter(d))] is not O(1) on current dict implementation.

   We are talking about a dictionary of 512 items in the worst case. On such very tiny collection, benchmarking matters more than O(...) complexity ;-)
8. methane commented on Dec 18, 2017

   

   methane

   on Dec 18, 2017

   Member

   More actions

   We are talking about a dictionary of 512 items in the worst case. On such very tiny collection, benchmarking matters more than O(...) complexity ;-)

   You're right. Rob Pike said:

   "Fancy algorithms are slow when n is small, and n is usually small."
   http://users.ece.utexas.edu/~adnan/pike.html
9. methane commented on Dec 18, 2017

   

   methane

   on Dec 18, 2017

   Member

   More actions

   • del cache[next(iter(cache))] happens only when sre.compile() is called.
   • del cache[next(iter(cache))] is much faster than sre.compile().

   OK, performance difference is negligible, surely.
10. serhiy-storchaka commented on Mar 11, 2018

    

    serhiy-storchaka

    on Mar 11, 2018

    MemberAuthor

    More actions

    New changeset b931bd0 by Serhiy Storchaka in branch 'master':
    bpo-32338: OrderedDict import is no longer needed in re. (bpo-4891)
    b931bd0
11. miss-islington commented on Mar 11, 2018

    

    miss-islington

    on Mar 11, 2018

    Contributor

    More actions

    New changeset 39441fc by Miss Islington (bot) in branch '3.7':
    bpo-32338: OrderedDict import is no longer needed in re. (GH-4891)
    39441fc
12. serhiy-storchaka

    closed this as completedon Mar 11, 2018
13. ezio-melotti

    transferred this issue fromon Apr 10, 2022

Issue actions