[pyar] Limitando size del input Queue de multiprocessing.Pool

[Alejandro Santos]

2014-04-07 15:30 GMT+02:00 Claudio Freire <klaussfreire en gmail.com>:
> 2014-04-07 10:25 GMT-03:00 Alejandro Santos <listas en alejolp.com>:
>>> Esto va a convertir tu BFS en DFS, pero es la única manera de evitar
>>> el deadlock y reducir el consumo de memorioa - el alto consumo de
>>> memoria es inherente a BFS.
>>>
>>
>> Supongamos que el problema anterior lo resolves, de forma que los
>> nodos que estan a menos de X de distancia del nodo inicial los
>> paralelizas como un BFS, y los que estan a mas de X de distancia del
>> inicial los procesar como DFS, vas a volver al problema original: el
>> elevado uso de memoria, la diferencia que antes estaba en la Queue del
>> BFS y ahora tenes tu backlog en el stack del worker.
>
>
> No, para nada.
>
> BFS consume memoria proporcional a la anchura del árbol (para grafos
> es algo más complicado).
>
> DFS consume memoria proporcional a la profundidad.
>

Pero aca estamos paralelizando tareas, por lo que un BFS paralelo
consume memoria O(anchura del arbol dividido la cantidad de workers),
y el DFS consume memoria O(profundidad multiplicada la cantidad de
workers).

De todas formas no quiero decir que el DFS no funcione, al contrario
me parece interesante para probar :)

> No es exactamente lo mismo, y para páginas web, con un alto índice de
> conectividad, la anchura puede ser considerable.
>
> También, pensándolo mientras escribo esta respuesta... ¿deduplicás los
> links antes de meterlos en la cola?
>

Disclaimer: no tengo nada que ver con W3AF, solamente me resulto
atractivo el problema :)

(y en algun momento hace muchos a;os use w3af y me parecio una
herramienta interesante)

> Estoy pesnado que tu problema puede ser simplemente, teniendo en
> cuenta que las páginas web suelen estar altamente conectadas, que
> guardás ~N² copias de los links.
>

Estimo que el web crawler no visita dos veces el mismo link,
guardandolo en alguna estructura compartida entre los workers,
convirtiendo el grafo en un arbol.

-- 
Alejandro Santos