Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here's a fuller interactive session that will help me explain what's going on (Python 2.6 on Windows XP 32-bit, but it doesn't matter really):</p> <pre><code>&gt;&gt;&gt; import sys &gt;&gt;&gt; sys.getsizeof([]) 36 &gt;&gt;&gt; sys.getsizeof([1]) 40 &gt;&gt;&gt; lst = [] &gt;&gt;&gt; lst.append(1) &gt;&gt;&gt; sys.getsizeof(lst) 52 &gt;&gt;&gt; </code></pre> <p>Note that the empty list is a bit smaller than the one with <code>[1]</code> in it. When an element is appended, however, it grows much larger.</p> <p>The reason for this is the implementation details in <code>Objects/listobject.c</code>, in the source of CPython. </p> <h2>Empty list</h2> <p>When an empty list <code>[]</code> is created, no space for elements is allocated - this can be seen in <code>PyList_New</code>. 36 bytes is the amount of space required for the list data structure itself on a 32-bit machine.</p> <h2>List with one element</h2> <p>When a list with a single element <code>[1]</code> is created, space for one element is allocated in addition to the memory required by the list data structure itself. Again, this can be found in <code>PyList_New</code>. Given <code>size</code> as argument, it computes:</p> <pre><code>nbytes = size * sizeof(PyObject *); </code></pre> <p>And then has:</p> <pre><code>if (size &lt;= 0) op-&gt;ob_item = NULL; else { op-&gt;ob_item = (PyObject **) PyMem_MALLOC(nbytes); if (op-&gt;ob_item == NULL) { Py_DECREF(op); return PyErr_NoMemory(); } memset(op-&gt;ob_item, 0, nbytes); } Py_SIZE(op) = size; op-&gt;allocated = size; </code></pre> <p>So we see that with <code>size = 1</code>, space for one pointer is allocated. 4 bytes (on my 32-bit box).</p> <h2>Appending to an empty list</h2> <p>When calling <code>append</code> on an empty list, here's what happens:</p> <ul> <li><code>PyList_Append</code> calls <code>app1</code></li> <li><code>app1</code> asks for the list's size (and gets 0 as an answer)</li> <li><code>app1</code> then calls <code>list_resize</code> with <code>size+1</code> (1 in our case)</li> <li><code>list_resize</code> has an interesting allocation strategy, summarized in this comment from its source.</li> </ul> <p>Here it is:</p> <pre><code>/* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize &gt;&gt; 3) + (newsize &lt; 9 ? 3 : 6); /* check for integer overflow */ if (new_allocated &gt; PY_SIZE_MAX - newsize) { PyErr_NoMemory(); return -1; } else { new_allocated += newsize; } </code></pre> <h2>Let's do some math</h2> <p>Let's see how the numbers I quoted in the session in the beginning of my article are reached.</p> <p>So 36 bytes is the size required by the list data structure itself on 32-bit. With a single element, space is allocated for one pointer, so that's 4 extra bytes - total 40 bytes. OK so far.</p> <p>When <code>app1</code> is called on an empty list, it calls <code>list_resize</code> with <code>size=1</code>. According to the over-allocation algorithm of <code>list_resize</code>, the next largest available size after 1 is 4, so place for 4 pointers will be allocated. 4 * 4 = 16 bytes, and 36 + 16 = 52.</p> <p>Indeed, everything makes sense :-)</p>
    singulars
    1. This table or related slice is empty.
    1. POSize of list in memory
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USEli Bendersky
    1. USEli Bendersky
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POSize of list in memory
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO@eryksun: you're right. updated, thanks.
      singulars
      1. PO
      1. USEli Bendersky
    2. COThat's the standard allocation strategy for List.append() across all programming languages / libraries that I've encountered. I think I would have guessed this is the cause without reading your answer (but now I have read it, so I can't really know). Anyway, nice detailed answer.
      singulars
      1. PO
      1. USripper234
    3. CO@ripper234: yes, the allocation strategy is common, but I wonder about the growth pattern itself. Textbook examples of amortized-linear runtime are usually mentioning powers-of-2. This seems like an unusual pattern, that *still* satisfies the formulae for linear behavior - I find this very interesting
      singulars
      1. PO
      1. USEli Bendersky
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload