How can loosely typed language have constant lookup time for an array?

Question

If I have an integer array "arr" of length 10 in C, to look up arr[5] the program can simply add 20 to the current pointer location and retrieve my value (constant time).

But if the array is loosely typed(python/javascript list) how can the pointer know in constant time where an element is? Since it can no longer assume that each element is fixed bytes.

Answer 1

You can check Python's source code - listobject.h:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

We can see here that Python's list is just an array of pointers to PyObject. So to access 5th element we simply need to take ob_item[5] which will just add 20 (40) to the value of pointer ob_item.

You can see the actual code in listobject.c:

static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
    ...
    Py_INCREF(a->ob_item[i]);
    return a->ob_item[i];
}