Memoria: la creazione di un grande insieme contro la fusione delle molte piccoli insiemi

Question

ho usato la funzione magica %memit per misurare l'utilizzo della memoria:

In [1]: %memit n = pow(10, 7); range(n) 
peak memory: 568 MiB, increment: 272 MiB 

In [2]: %memit n = pow(10, 7); set(xrange(n)) 
peak memory: 824 MiB, increment: 447 MiB 

OK così sembra che ci sia una fase intermedia in cui xrange(n) viene istanziato in un elenco completo . Ma cosa succede se taglio la mia lista in 10 sottoliste e le unisco a una a una? Questo sarebbe più efficiente in termini di memoria, giusto?

In [3]: %memit n = pow(10, 7); reduce(set.union, (set(xrange(p, n, 10)) for p in range(10))) 
peak memory: 1260 MiB, increment: 897 MiB 

Beh, che non è andato come previsto. Perché l'approccio reduce consuma più memoria di set(xrange(n))?

Answer 1

Ci sono molti equivoci da chiarire. Prima di tutto, un xrange è non trasformato in un elenco prima che sia trasformato in un set in set(xrange(n))!

La memoria picco per l'approccio reduce deriva dal fatto che set.union restituisce un valore nuova che è un'unione dei 2 set di risultati. E reduce memorizza internamente un valore aggiuntivo, il accum_value. Così sull'ultima iterazione di tale for ciclo:

accum_value = function(accum_value, x) 

Il accum_value che va nella funzione contiene 90% di 10⁷ elementi, x contiene 10% di 10⁷ elementi, ma il valore restituito sarà necessario spazio per tutti 10⁷ elementi . Lo spazio per tutti questi deve essere prenotato contemporaneamente. Solo dopo che function è stato restituito, viene rilasciata la memoria per il vecchio accum_value e x.

---

Tuttavia questa non è ancora la fine. La memoria di picco indica la quantità di memoria necessaria in nel processo, ma non quanto è in uso dopo l'operazione completata se il set era ancora esistente.

Così un benchmark differente è necessario:

In [1]: %memit n = pow(10, 7); result = set(xrange(n)); 
peak memory: 522.22 MiB, increment: 498.93 MiB 
In [2]: %memit 42 
peak memory: 513.83 MiB, increment: 0.12 MiB 
In [3]: import sys 
In [4]: sys.getsizeof(result) 
Out[4]: 268435688 

e

In [1]: %memit n = pow(10, 7); result = reduce(set.union, (set(xrange(p, n, 10)) for p in range(10))); 
peak memory: 1063.20 MiB, increment: 1039.71 MiB 
In [2]: %memit 42 
peak memory: 779.77 MiB, increment: 0.00 MiB 
In [3]: import sys  
In [4]: sys.getsizeof(result) 
Out[4]: 536871144 
In [5]: 536871144.0/268435688 
Out[5]: 1.9999991357333977 

Quindi l'utilizzo della memoria per la reducescende a 778 MiB dopo l'esecuzione; tuttavia è ancora più che per il caso di costruzione di set più semplice. E come potete vedere, lo set(xrange(n)) non ha bisogno di molta memoria interna, poiché l'utilizzo della memoria diminuisce di appena 9 MiB dopo che il set è stato costruito.

In particolare, non solo l'approccio reduce è più lento; il set risultante consuma anche il doppio della memoria. Questo perché un set è supportato da un hashtable e viene ingrandito ogni volta che si ritiene che abbia troppe collisioni. Hai incontrato un comportamento patologico in cui l'insieme degli stessi valori si traduce in uno che occupa il doppio della memoria dell'altro.

Answer 2

Per the docs, reduce è grosso modo equivalente a:

def reduce(function, iterable, initializer=None): 
    it = iter(iterable) 
    if initializer is None: 
     try: 
      initializer = next(it) 
     except StopIteration: 
      raise TypeError('reduce() of empty sequence with no initial value') 
    accum_value = initializer 
    for x in it: 
     accum_value = function(accum_value, x) 
    return accum_value 

scorrere il iterable, (set(xrange(p, n, 10)) for p in range(10)), richiede circa 447 MiB. Si potrebbe pensare che dal momento che questo iterabile è un generatore di espressione si risparmia memoria, ma interi sono saved in an internal free list:

“Per la velocità”, Python mantiene una lista libera interna per gli oggetti interi. Sfortunatamente, quella lista libera ha dimensioni immortali e illimitate.

Quindi, una volta che ogni set è stato istanziato, la maggior parte della memoria che consuma non viene mai liberata.

Il valore restituito accum_value richiede anche circa 447 MiB. Insieme, la chiamata a reduce richiede quindi circa 447 + 447 = 894 MiB.