Opinion sobre los array en Python

[Hernan Foffani]

[lamento no poder responder puntualmente a cada cosa por falta
de tiempo en el trabajo y de conexion a internet en casa, mis
respuestas quedan así algo desfasadas.]

Antonio Castro escribio:
> On Fri, 16 Apr 2004, Hernan Foffani wrote:
>> para hacer la comparación equivalente deberías considerar como
>> *minimo* que:
>>   1. las listas de python son de tamaño dinámico. (vuelve a
>>   codificar los dos programas permitiendo que las pruebas se
>>   hagan con distintos tamaños especificados por linea de comandos)
>>   2. las listas de python alojan objetos de cualquier tipo.
>
> Tambien lo sé, pero precisamente por eso son ineficientes cuando lo
> que se trata es de hacer algo muchísimo más sencillo.

Entiendo tu insatisfacción.  Lo que estoy tratando de explicar, y por
lo visto no lo estoy haciendo muy bien, es que no es posible para
python "hacer algo muchísimo mas sencillo".

>>   main() { printf("Comienzo\n"); printf("End\n"); }
>> ;-)
>
> Tu fijate bien lo que estas diciendo. El código genera una serie de
> instrucciones porque se produce un resultado en el interiora del array
> (tabla1).

para ser mas preciso, si el array tabla1 estuviera declarado como static
(de hecho esa debería ser la intención del programador a un .c que no
enlaza con ningun otro modulo) el compilador podría generar codigo como
el anterior.

lo que quiero decir con todo esto es que
  a) en el estado actual de la implementación del lenguaje y
  b) si se sigue respetando la filosofia de python
no es posible obtener los resultados que pretendes *aun con la
incorporacion en python de un tipo de datos array*

>> además, en el estado actual del parser/compilador/interprete de
>> python, pasarle al constructor de la lista un "elem_muestra" es
>> irrelevante.  (hoy) no hay nada que pueda hacer mejor (o mas rapido)
>> sabiendo que todos los elementos serán de tipo int o cualquier
>> otra cosa.
>
> Exacto lo has captado. Este es el problema de hoy.

Si. Pero desgraciadamente no se resuelve con un tipo de datos array.

>> optimizar python no es sencillo.  hay varias alternativas en
>> uso y en estudio.  desde generar codigo C a partir de anotaciones
>> y/o extensiones al lenguaje hasta ideas sobre compiladores JIT.
>
> No sirve para este caso por las razones que dije en el mensaje
> anterior. Si no se da algún soporte en el propio lenguaje el
> resultado no será eficiente.

No se por qué presupones que las alternativas en estudios no
se incorporarán al lenguaje.  Se está trabajando muchisimo, dentro
de los pocos recursos que se disponen, en la evolución del
lenguaje.

Intentaré ser mas especifico en mi respuesta para evitar caer en
un "tu dices no. yo digo si".

Las listas en python ya *son* implementadas internamente como un
un vector dinámico en C.  Un extracto del codigo en
Object/listobject.c lo muestra claramente:

PyObject *
PyList_New(int size)
{
	PyListObject *op;
	size_t nbytes;
   ...
	nbytes = size * sizeof(PyObject *);
   ...
	op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
   ...
	op->ob_size = size;
	op->allocated = size;
	return (PyObject *) op;
}

(PyList_New sería el equivalente al constructor de la lista, he quitado
testeo de errores para que quede mas claro)
Como ves, el resultado de PyList_New es un vector *contiguo* de
punteros.  El acceso a cada elemento se hace por artimetica de punteros.
Python lo hace así desde 1990.

El problema es que *todos* los tipos de datos de python son *objetos*
por lo que NO es posible optimizar
    mi_array[4] = 3
a un par de instrucciones de ensamblador como lo haría un buen
compilador de C.
Como máximo python podría obtener la *referencia* al objeto en pocas
instrucciones de ensamblado (y nunca sería lo mismo que C ya que
python tiene que controlar los desbordes en tiempo real) pero
todavía resta el procesamiento de cada elemento del vector.

El '3' de la asignacion anterior es un objeto como cualquier otro.
Si se quiere igualar la velocidad de C en bucles como el ejemplo
que has mencionado no basta con un tipo de datos array como el que
propones.  Que los elementos sean todos enteros o todos tuplas
o una mezcla heterogenea de objetos es irrelevante para el *array*
en sí mismo.

El problema de python se "reduce" a tener que transformar el '3'
de objeto int (que en python tiene propiedades especiales como el
hecho que el valor maximo de un entero está acotado *solo* por la
memoria disponible en tu ordenador) a los 16 o 32 bits de internos
del procesador.

En otras palabras, la enorme dificultad de optimizar
   mi_array[4] = 3
no está en la implementacion de 'mi_array' sino en el '3' (y
también en el '4')

Por supuesto que es sencillo hacerlo con constantes, pero ¿cuanto
nos beneficiaria eso?  No hay muchas aplicaciones por allí donde
todos los enteros son constantes.

La verdad es que este caso particular el compilador de python
lo hace bastante bien.

>>> import dis
>>> def f():
	mi_array[4] = 3


>>> dis.dis(f)
  2           0 LOAD_CONST               1 (3)
              3 LOAD_GLOBAL              0 (mi_array)
              6 LOAD_CONST               2 (4)
              9 STORE_SUBSCR
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE
>>>

Lo que hace python aquí es "acelerar" la creación del objeto entero
con la instrucción LOAD_CONST.

Para que igualar los ordenes de magnitud de C, la implementación de
STORE_SUBSCR para un objeto list debería convertir las constantes
'3' y '4' de objetos python a enteros nativos del procesador.

Desgraciadamente un programa no consta de constantes:

>>> def g():
	entero = 5
	mi_array[4] = entero


>>> dis.dis(g)
  2           0 LOAD_CONST               1 (5)
              3 STORE_FAST               0 (entero)

  3           6 LOAD_FAST                0 (entero)
              9 LOAD_GLOBAL              1 (mi_array)
             12 LOAD_CONST               2 (4)
             15 STORE_SUBSCR
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE
>>>

Y peor aun si lo complicamos apenitas:

>>> def h():
	entero = 5
	funcion(entero)
	mi_array[4] = entero


>>> dis.dis(h)
  2           0 LOAD_CONST               1 (5)
              3 STORE_FAST               0 (entero)

  3           6 LOAD_GLOBAL              1 (funcion)
              9 LOAD_FAST                0 (entero)
             12 CALL_FUNCTION            1
             15 POP_TOP

  4          16 LOAD_FAST                0 (entero)
             19 LOAD_GLOBAL              2 (mi_array)
             22 LOAD_CONST               2 (4)
             25 STORE_SUBSCR
             26 LOAD_CONST               0 (None)
             29 RETURN_VALUE
>>>

Un buen compilador de C convertiría lo anterior en 4 o 5
instrucciones de ensamblado, ¿puede python hacer lo mismo?
No, por las razones a y b que escribí al principio de
este mensaje.

En particular la dificultad mas grande para un optimizador
de python es deducir si podría reemplazar
             16 LOAD_FAST                0 (entero)
por
             16 LOAD_CONST               1 (5)
y luego convertir la constante en entero nativo.
Pero para eso debe detectar que la llamada a 'funcion(entero)'
no cambia el tipo ni el valor de 'entero' (detectar que
'funcion' es una funcion pura)


En resumen:
Cambiar PyList_New(int size) a algo como PyListFloat_New(size)
que haga 'nbytes = size * sizeof(float);' es el menor de
los problemas.
La dificultar reside es predecir el tiempo de vida (en flujo de
programa no en segundos) de los objetos sobre todo de aquellos se
podrían implementar como nativos.

Dicho de otra forma. Disponer de una estantería especialmente
diseñada para alojar con eficacia hojas A4 es inutil si
no puedo saber de antemano que las 'cosas' que tengo que
guardar y recuperar son folios de este tipo.

Hay alternativas en estudio *dentro* del lenguaje.  Un proyecto
interesante es Psyco.  Es un 'specialized compiler' (no se si la
traduccion literal es el nombre academico.)
Otros están estudiando algoritmos de predicción de tipos mediante
analisis de flujo de programa o mediante analisis en tiempo de
ejecución.  Otra aproximación es un python con anotación de tipos.
Por desgracia ninguna es trivial.


Espero haberme explicado mejor.

Saludos,
-H.