3 ms·

I think you have a point about C or C++ notion of arrays having the same type. I'll probably rewrite that paragraph, since the main point is to tell people unf

I think you have a point about C or C++ notion of arrays having the same type. I'll probably rewrite that paragraph, since the main point is to tell people unfamiliar with Python that lists aren't actually linked lists.

Waterluvian 8y ago
So... Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Then in cpython the actual list contents are Python objects sitting on the heap in a non-contiguous manner? And when the list needs to be resized and doubles itself, it's just doubling the space for object references?
- haikuginger 8y ago
  > So... Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Yes. Every Python object is held by the interpreter as a pointer to a PyObject struct on the (C) heap.
  - aggerdom 8y ago
    Not something I would put into production, but had a fun application of this on a side project. I had the `id` of a function (but not the function object itself) and needed to recover the function. In CPython, `id` of a function corresponds to it's memory address (not sure if that can be overridden). By casting the id to a PyObject, I was able to recover the original. func = ctypes.cast(int(address), ctypes.py_object).value Was kinda cool actually seeing that work.
- eatitraw 8y ago
  > Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Yep, it is an array of pointers: https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23 https://github.com/python/cpython/blob/3.7/Include/listobjec... > And when the list needs to be resized and doubles itself, it's just doubling the space for object references? Basically yes. The growth pattern is not as aggressive as doubling though: https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L55 https://github.com/python/cpython/blob/3.7/Objects/listobjec...
  - Waterluvian 8y ago
    I keep forgetting just how readable cpython source is. I'm still mentally stuck in my beginner years, where it was all Greek to me. Thanks for sharing these links.
  - mcguire 8y ago
    Interesting: "The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ..." What is the big-o amortized cost of using this pattern? Doubling has a easy proof that it's O(1) amortized.
    - eatitraw 8y ago
      The growth pattern is still exponential, instead of going x -> 2 * x, you go x -> 9/8 * x + 6. I think it should still be O(1) amortized, you just need to adjust your proof for doubling a bit.
    - rurban 8y ago
      Mathematically the best is not doubling but fibonacci. for the start doubling is used because it's much faster to compute.

Waterluvian 8y ago

So... Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Then in cpython the actual list contents are Python objects sitting on the heap in a non-contiguous manner? And when the list needs to be resized and doubles itself, it's just doubling the space for object references?

haikuginger 8y ago
> So... Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Yes. Every Python object is held by the interpreter as a pointer to a PyObject struct on the (C) heap.
- aggerdom 8y ago
  Not something I would put into production, but had a fun application of this on a side project. I had the `id` of a function (but not the function object itself) and needed to recover the function. In CPython, `id` of a function corresponds to it's memory address (not sure if that can be overridden). By casting the id to a PyObject, I was able to recover the original. func = ctypes.cast(int(address), ctypes.py_object).value Was kinda cool actually seeing that work.
eatitraw 8y ago
> Because lists are dynamically typed and heterogeneous, does that mean the underlying C is basically a contiguous segment of memory of python object references? Yep, it is an array of pointers: https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23 https://github.com/python/cpython/blob/3.7/Include/listobjec... > And when the list needs to be resized and doubles itself, it's just doubling the space for object references? Basically yes. The growth pattern is not as aggressive as doubling though: https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L55 https://github.com/python/cpython/blob/3.7/Objects/listobjec...
- Waterluvian 8y ago
  I keep forgetting just how readable cpython source is. I'm still mentally stuck in my beginner years, where it was all Greek to me. Thanks for sharing these links.
- mcguire 8y ago
  Interesting: "The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ..." What is the big-o amortized cost of using this pattern? Doubling has a easy proof that it's O(1) amortized.
  - eatitraw 8y ago
    The growth pattern is still exponential, instead of going x -> 2 * x, you go x -> 9/8 * x + 6. I think it should still be O(1) amortized, you just need to adjust your proof for doubling a bit.
  - rurban 8y ago
    Mathematically the best is not doubling but fibonacci. for the start doubling is used because it's much faster to compute.