Optimize dict.fromkeys #3586

Activity

1. dieterplex commented on Mar 30, 2022

   

   dieterplex

   on Mar 30, 2022

   Last edited by dieterplex

   Contributor

   More actions

   Do you mean the cases that dictresize occurs when the keys are dict/set ?
2. Snowapril commented on Mar 30, 2022

   

   Snowapril

   on Mar 30, 2022

   Last edited by Snowapril

   Contributor

   More actions

   It seems if given iterable is exact set type or exact dict type(it means, the class that inherits dict or set is not the case), preallocate the memory for dict with the given length of iterable
   But I cant find the case when that (PyDictObject *)d)->ma_used does not have value 0.
   d is result of _PyObject_CallNoArg of given type thus there may not exist the case that the given type is exact dict type and not empty 😢
3. dieterplex commented on Mar 30, 2022

   

   dieterplex

   on Mar 30, 2022

   Contributor

   More actions

   >>> class x(dict):
   ...     def __new__(self):
   ...             return {key: None for key in [1,2,3,5,6,7]}
   ... 
   >>> x()
   {1: None, 2: None, 3: None, 5: None, 6: None, 7: None}
   >>> x.fromkeys("abc")
   {1: None, 2: None, 3: None, 5: None, 6: None, 7: None, 'a': None, 'b': None, 'c': None}
   >>> 
   

   Would this be the a valid case?

   👍React with 👍1Reacted by Snowapril
4. dieterplex commented on Mar 30, 2022

   

   dieterplex

   on Mar 30, 2022

   Contributor

   More actions

   Ah, that must be exact dict.
5. Snowapril commented on Mar 30, 2022

   

   Snowapril

   on Mar 30, 2022

   Last edited by Snowapril

   Contributor

   More actions

   @dieterplex Oh yes that is exactly the case that result of _PyObject_CallNoArg of given type is exact dict type and not empty, as __new__ of x return the non-empty exact dict. I checked it with debugger in cpython 😊
6. dieterplex commented on Mar 30, 2022

   

   dieterplex

   on Mar 30, 2022

   Last edited by dieterplex

   Contributor

   More actions

   In other words, it should be preallocate when meet conditions. But is there such a concept it could be preallocate for entries, a.k.a. DictContent?

   edit: Found DictInner::resize() inside dictdatatype::Dict.

   👍React with 👍1Reacted by Snowapril
7. dieterplex commented on Mar 31, 2022

   

   dieterplex

   on Mar 31, 2022

   Contributor

   More actions

   Implementing CPython like dictresize seems need put some effort to it. Alternatively, just route tomerge_object for specific conditions and add a TODO to follow up with a separate issue? @youknowone
   And where should I place the unit test file?
8. youknowone commented on Mar 31, 2022

   

   youknowone

   on Mar 31, 2022

   MemberAuthor

   More actions

   @dieterplex that sounds good. I don't feel like we necessarily need tests for the case, but you can put any original tests in extra_tests/snippets directory. Then CI will run every tests inside the directory.
9. Snowapril commented on Apr 7, 2022

   

   Snowapril

   on Apr 7, 2022

   Last edited by Snowapril

   Contributor

   More actions

   @dieterplex Hi. Are you currently working on this issue? If not, I would like to use this issue for the next sprint this weekend. Please tell me freely.
10. dieterplex commented on Apr 7, 2022

    

    dieterplex

    on Apr 7, 2022

    Contributor

    More actions

    Not yet, just go ahead no problem.
    I look into it and think about is there a way to replace entries without bulk insert?
11. Snowapril commented on Apr 7, 2022

    

    Snowapril

    on Apr 7, 2022

    Contributor

    More actions

    Thank 😊. If not used, I'll tell you again in this thread.
12. youknowone commented on Oct 6, 2026

    

    youknowone

    on Oct 6, 2026

    MemberAuthor

    More actions

    dict.fromkeys now has the CPython _PyDict_FromKeys fast path: exact dict/set keys reuse stored hashes (fromkeys_known_hashes) and an empty exact dict preallocates with reserve_for_empty (#8503, #8874).

    Closing.

    — commented by Grok 4.6
13. youknowone

    closed this as completedon Oct 6, 2026