#🔒 question about python dictionaries

28 messages · Page 1 of 1 (latest)

pure dew
#

how does python handle the increase and decrease dictionary "value" sizes? does it pre-allocate a certain amount of memory for each key-value pair, and if so, what happens if I append more data to an existing "value"? does it have to reallocate memory every time the value changes in size?

lethal charmBOT
#

@pure dew

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
zenith shore
#

A dictionairy just contains references to values

dense hull
#

umm

zenith shore
#

So if a value in the dict is a list, the dict would just contain information about where this list is stored in memory

#

And the list would manage the memory alocations of its values f.e.

pure dew
#

yeah, that was my impression

#

but say i add like

#

a significant number of values to this list

#

and as a result the list changes memory location

#

does the dictionary then reset its internal reference automatically

zenith shore
#

The dict would just reference to the list object. The list would keep track of where the values are stored (a list uses a C array iirc), so the dict woul not need to change anything.

pure dew
#

c arrays are preallocated and fixed from what I know, right? so increasing size beyond its preallocated size requires a full copy operation to a different memory location.

#

though thats besides the point - what happens within a dictionary if an object stored within changes memory location?

#

sorry for the trouble, just not sure how they work - i tend to be pretty pedantic when it comes to references to objects that move around

#

i'm assuming for now that python does some magic that ensures the reference stored within the dict constantly follows the object

vivid wadi
#

Python list objects are supposedly on the heap, so I think they're allocated with malloc() or realloc(), and realloc() and either resizes the memory block, or allocates a new one and copies stuff over. But I'm not a Python or even C whiz, and I certainly haven't looked. 🙂

pure dew
#

so how do python dictionaries handle references to objects that have moved? does the reference change with it? how does the dictionary know when and where to change its reference to?

slow warren
#

A CPython object contains all those references. Python variable are references to the object structure. So the object base structure doesn't move.

meager haven
# pure dew how does python handle the increase and decrease dictionary "value" sizes? does ...

It pre-allocates more space than it needs and uses a simple equation to decide how much to grow by each time it needs to expand.

This would be a good overview of the specifics of dictionaries: https://github.com/python/cpython/blob/6c09b8de5c67406113e8d082e05c9587e35a852a/Objects/dictobject.c#L1

Here's where dictionaries are resized:
https://github.com/python/cpython/blob/6c09b8de5c67406113e8d082e05c9587e35a852a/Objects/dictobject.c#L1876

And I believe this is the main function used to calculate the new size on resize:
https://github.com/python/cpython/blob/6c09b8de5c67406113e8d082e05c9587e35a852a/Objects/dictobject.c#L569

lethal charmBOT
#

Objects/dictobject.c line 1

/* Dictionary object implementation using a hash table */```
`Objects/dictobject.c` line 1876
```c
Restructure the table by allocating a new table and reinserting all```
`Objects/dictobject.c` line 569
```c
estimate_log2_keysize(Py_ssize_t n)```
meager haven
lethal charmBOT
#

Objects/dictobject.c line 1614

insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)```
pure dew
#

thanks a lot, i'll have a look through the docs

#

appreciate the help

#

!close

lethal charmBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.