Как стать автором
Обновить

Комментарии 30

НЛО прилетело и опубликовало эту надпись здесь
Спасибо, я, конечно, думал про целые числа (как противоположность дробным), а про «простые».
Немного на ту же тему.
Как-то надо было по быстрому обработать ~11млн простых структур (полями были целочисленные и короткие строковые поля). Хотел на python, но ему не хватило 8Г оперативки :( В итоге было переписано на C.
Вот тогда я почувствовал, насколько python прожорлив.
Numpy Вам в помощь.
Да задача решена еще тогда была (на C памяти заняло около 2Г). Не ожидал на тот момент, что python окажется настолько прожорливым.
Ну может всетакие надо было заюзать итераторы? А то 11 милион структур в памяти держать — имхо не лучшее решение. Напоминает решения из серии — я не могу собрать кубик Рубика, я его молоточком а потом суперклеем :)
Давайте не будем обсуждать дальше решение в топике не про него) Можно в личке, если хочется.
Просто странно видеть заявление, что Питон прожорлив, если та же задача на Си заняла 2 Гб памяти. Если бы задача появилась на 3 года раньше и у вас была машина с 1Гб памяти, прожорлив был бы Си?

В данном случае прожорлив не Си или Питон, а метод, которым вы решали задачу.
Простите, но… вы хотели запихнуть 11млн простых структур в память, чтобы их обработать?
Да, был файл, содержащий данные с неким подобием RTL сжатия. ~11млн это уже после обработки одинаковых значений (что-то вида 500 одинаковых значений подряд в столбце или 3000 одинаковых подряд в строке).
А точно нужно было в памяти всё сразу держать? Часто можно код организовывать так, чтоб это не требовалось. В Python для этого всякие плюшки есть — генераторы, модуль itertools. Значительно удобнее, чем на C :) Занимало бы тогда мегабайт 50 вместо 2 гигабайт.
Потому и был взят python, чтобы быстро и просто сбацать обработку :) Данные хранились поколоночно, но при этом могла быть отметка «эту ячейку повторить в строке N раз». А результат обработки нужно было сохранять построчно в другом формате. И 2Г — это на C, питон выедал 7.5Г и убивался OOM killer'ом.
Не держать все одновременно может бы и вышло, но логика получилась бы совсем не тривиальная. А ведь кроме считывания там основной объем занимала обработка :)
В общем, на C это легло хорошо и быстро.
С целыми числами не все так просто, кстати :) В CPython есть так называемые «free lists» — куски памяти, выделяемые под объекты заранее, чтоб не вызывать malloc по многу раз. Есть отдельные free lists для различных встроенных типов (словарей, кортежей, чисел и т.д.)

Так вот, если для словарей и кортежей размер free list ограничен (1000 что-ли объектов), то в Python 2.x размер free list для чисел не ограничен. Это означает, что если в памяти в какой-то момент одновременно находится миллион разных целых чисел (экземпляров int), то они останутся там навсегда (до завершения процесса). Сборщик мусора этим всем не занимается, т.к. к сборке мусора это все отношения не имеет. Пробежались по xrange(1000000) — все ок, пробежались по range(1000000) — миллион объектов int остался в памяти навсегда.

В одной из 3.х версий это как-то обошли.

Ну и, понятное дело, если важно, сколько миллион чисел занимает, то его лучше хранить в array.array (или numpy.ndarray), чтоб не создавать ненужные объекты int и убрать оверхед на все эти указатели.
Звучит как баг и не очень понятно, при чём тут free list. Пример же на сравнении xrange() и range() сравнивает функцию-генератор и функцию, генерирующую список.
Тут или Вы чего-то не поняли, или это реально баг в Python 2.x.

Можно пример кода, который подтверждал бы это? Висение миллиона интов легко видно по потреблению процессом памяти.
Легко :)

# примеры для Python 2.7
def create_temp_strings():
    temp_value = [str(x) for x in xrange(10000000)]  
    
def create_temp_ints():
    temp_value = [x*2 for x in xrange(10000000)]

Если вызвать функцию create_temp_strings(), то она в пике займет мегабайт 700 памяти, но после завершения потребление памяти вернется к прежнему уровню. Если вызвать create_temp_ints(), то под Python 2.7 она займет в пике мегабайт 250, и они так и останутся занятыми после ее завершения. И там, и там используется xrange; разница в том, что в create_temp_strings() инты не находятся в памяти одновременно, а перебираются по одному. То, что все строки находятся в памяти одновременно, к проблеме не ведет, т.к. для строк объем преаллокации ограничен.

См., например, примечания к docs.python.org/2/library/gc.html#gc.collect и deeplearning.net/software/theano/tutorial/python-memory-management.html#internal-memory-management

Я, может, неправильно это все «free lists» называю — там для чисел вроде списки пулов, а не просто списки. Но это уже детали.
bugs.python.org/issue1338264 — вот issue 2005 года про это, для Python 2.4, закрыт как wont fix :) Цитата:

Space for integer objects in particular lives in an immortal free list of unbounded size… If you don't want that, don't do that ;-)
Спасибо за примеры, надо будет порыть на досуге… :)
Есть у меня на примете питоновые штуки, которые едят память как не в себя, пробую их покусать с разных сторон. Могу попробовать оформить «покусанное» в виде мыслей/вопросов о том, как исследовать потребления памяти, кстати, если интересно. Правда, выводов и готовых рецептов пока нет. :(
Попробовал, что-то в этом действительно есть.
Правда, для 2.6+ похоже, что часть статей устарела (в некотором смысле), и эти free list'ы можно чистить.

Их чистит gc.collect() при вызове с максимальной генерацией (обычно это gc.collect(2)), проверял на Вашем примере с функциями.
Правда, как часто вызывается такая сборка мусора (и вызывается ли вообще) — я не знаю.
Смотрим официальную документацию (GC):

gc.collect([generation])

Изменения в версии 2.6. Free list-ы для некоторых встроенных типов очищаются, когда выполняется полная очистка или очистка с максимальной генерацией (2). Ввиду особенности реализации, некоторых объекты во free list-ах могут не удалятся, в частности, int и float.

Насколько я понимаю, в нашем случае это верно. Никакого видимого эффекта после вызова gc.collect(2) не произошло.
Странно, я читал исходники 2.7.5, и там список int'ов вполне себе чистится (в том случае, если эти int'ы не используются, т.е. их refcount = 0).
И вызов gc.collect(2) у меня приводил к тому, что память освобождалась (для вышеприведённого примера с функцией), проверял на Win ActiveState Python 2.7.2 x86_64.
Может, у Вас версия другая какая?..
Посмотрел сейчас внимательно в код (Objects/intobject.c, функция PyInt_ClearFreeList), часть int'ов может быть не очищена при очистке free list'a, поскольку последний хранится в виде связного списка небольших массивов, и каждый массив удаляется только в том случае, если в нём остались только int'ы с нулевым количеством ссылок (т.е. один «живой» int будет держать весь массив).
Похоже, я был зомбирован статьями и комментариями в интернете, которые уже успели устареть. Почитал исходный код и кое-чего уяснил. Я попробую проиллюстрировать свои открытия на примерах, но сначала немного теории…

Объекты Int (как и некоторые другие встроенные типы) поддерживают собственный аллокатор памяти. При необходимости память запрашивается вызовом malloc (в коде используется макрос PyMem_MALLOC, но это просто обертка вокруг malloc; не путать с PyMem_Malloc) блоками по ~1kb.

Есть два связанных списка: block_list — список всех выделенных блоков памяти и free_list — список всех свободных ячеек в этих блоках. Когда создается новый Int, то первым делом (еще есть кэширование значений от -5 до 256, но не будем об этом...) проверяется указатель free_list. Если он не равен null, то Int записывается в свободную ячейку, а free_list укорачивается на один элемент. Если null, то значит, свободных ячеек больше нет. В этом случае вызывается функция fill_free_list, которая запрашивает у malloc новый блок и добавляет его ячейки в список free_list.

Когда количество ссылок на Int становится равно нулю, его адрес добавляется в конец списка free_list.
Посмотреть картинки и подробнее почитать обо всем этом можно здесь: www.laurentluce.com/posts/python-integer-objects-implementation/

Также есть функция PyInt_ClearFreeList, которая отыскивает среди block_list-ов такие, которые полностью состоят из свободных ячеек, вырезает их из списка и вызывает на них malloc_free (опять через обертку PyMem_FREE). Эта функция (в первоначальном название PyInt_CompactFreeList) была добавлена в версии python 2.6 alpha 1 (см. bugs.python.org/issue1953). Следующие комментарий в начале модуля intobject.c явным образом отрицает ее существование, потому что он был написан на 6 лет раньше и с тех пор не обновлялся. Не верьте ему :).

hg blame intobject.c
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000: /* Integers are quite normal objects, to make object handling uniform.
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    (Using odd pointers to represent integers would save much space
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    but require extra checks for this special case throughout the code.)
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    Since a typical Python program spends much of its time allocating
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    and deallocating integers, these operations should be very fast.
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    Therefore we use a dedicated allocation scheme with a much lower
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    overhead (in space and time) than straight malloc(): a simple
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000:    dedicated free list, filled when necessary with memory from malloc().
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    block_list is a singly-linked list of all PyIntBlocks ever allocated,
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    linked via their next members.  PyIntBlocks are never returned to the
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    system before shutdown (PyInt_Fini).
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    free_list is a singly-linked list of available PyIntObjects, linked
       tim 01478a132908 Sun Apr 28 16:57:34 2002 +0000:    via abuse of their ob_type members.
     guido a6934380c6e7 Thu Dec 20 15:06:42 1990 +0000: */



Сама функция PyInt_ClearFreeList регулярно дергается сборщиком мусора. Вот так выглядит ее вызов в версии 2.7.5:

Modules/gcmodule.c
/* This is the main function.  Read this to understand how the
 * collection process works. */
static Py_ssize_t
collect(int generation)
{
    …
    здесь много кода
    ...
    /* Clear free list only during the collection of the highest
     * generation */
    if (generation == NUM_GENERATIONS-1) {
        clear_freelists();
    }

/* Clear all free lists
 * All free lists are cleared during the collection of the highest generation.
 * Allocated items in the free list may keep a pymalloc arena occupied.
 * Clearing the free lists may give back memory to the OS earlier.
 */
static void
clear_freelists(void)
{
    (void)PyMethod_ClearFreeList();
    (void)PyFrame_ClearFreeList();
    (void)PyCFunction_ClearFreeList();
    (void)PyTuple_ClearFreeList();
#ifdef Py_USING_UNICODE
    (void)PyUnicode_ClearFreeList();
#endif
    (void)PyInt_ClearFreeList();
    (void)PyFloat_ClearFreeList();
}



Итак, обещанные примеры.
Для наблюдения за расходом памяти я использовал memory_profiler в связке с psutil. Чтобы освободить память я напрямую дергаю PyInt_ClearFreeList (через ctypes.pythonapi) и, на всякий случай, gc.collect(2), чтобы доказать, что ничего нового не произойдет.

Пример 1. Здесь все хорошо.
Filename: tests/test_good.py

Line #    Mem usage    Increment   Line Contents
================================================
     6                             @profile
     7     5.785 MB     0.000 MB   def func():
     8    21.117 MB    15.332 MB       a = range(10**6)
     9    17.301 MB    -3.816 MB       del a
    10     5.895 MB   -11.406 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    11     5.895 MB     0.000 MB       gc.collect(2)



Мы забрали память у ОС, а потом его вернули. Вот бы так было всегда…

Пример 2. Что-то настораживает...
Filename: tests/test_bad.py

Line #    Mem usage    Increment   Line Contents
================================================
     6                             @profile
     7     5.781 MB     0.000 MB   def func():
     8    21.117 MB    15.336 MB       a = range(10**6)
     9    21.117 MB     0.000 MB       b = int('300')
    10    17.301 MB    -3.816 MB       del a
    11    17.309 MB     0.008 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    12    17.309 MB     0.000 MB       del b
    13     5.895 MB   -11.414 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    14     5.895 MB     0.000 MB       gc.collect(2)



Мы создали кучу Int-ов, затем создали еще один, а потом нашу кучу удалили. В итоге память в ОС не вернулось. Только после того как мы удалили последний Int (и, соответственно, освободился block_list, который он «держал») память наконец-то вернулась на место. Здесь вместо int('300') могли бы быть любые расчеты и прочие операции, которые создают Int-ов.

Можно ли как-то избежать освобождения последнего block_list-а?

Пример 2а. Грязный хак.
Filename: tests/test_bad_hack.py

Line #    Mem usage    Increment   Line Contents
================================================
     6                             @profile
     7     5.789 MB     0.000 MB   def func():
     8    21.117 MB    15.328 MB       a = range(10**6)
     9    21.117 MB     0.000 MB       b = int('300')
    10    17.301 MB    -3.816 MB       del a
    11    17.309 MB     0.008 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    12     5.785 MB   -11.523 MB       libc.malloc_trim(0)
    13                                 #del b
    14     5.785 MB     0.000 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    15     5.785 MB     0.000 MB       gc.collect(2)


Здесь мы вызываем функцию malloc_trim из libc и все становиться на место. В примере это сработало, но я бы не стал использовать такой трюк в реальном проекте.
Еще пару примеров можно почитать здесь:
nuald.blogspot.ru/2013/06/memory-reclaiming-in-python.html
bugs.python.org/msg134008

Пример 3. Грустный..
Filename: tests/test_ugly.py

Line #    Mem usage    Increment   Line Contents
================================================
     6                             @profile
     7     5.781 MB     0.000 MB   def func():
     8     5.781 MB     0.000 MB       i = 0
     9     5.781 MB     0.000 MB       a = []
    10    13.094 MB     7.312 MB       while i < 10**5:  # 10**5 чтобы было быстрее
    11    13.094 MB     0.000 MB           a.append(i)
    12    13.094 MB     0.000 MB           i += 1
    13    12.711 MB    -0.383 MB       del a
    14    12.711 MB     0.000 MB       del i
    15    12.719 MB     0.008 MB       ctypes.pythonapi.PyInt_ClearFreeList()    
    16    12.711 MB    -0.008 MB       libc.malloc_trim(0)
    17    12.711 MB     0.000 MB       ctypes.pythonapi.PyInt_ClearFreeList()
    18    12.711 MB     0.000 MB       gc.collect(2)



Здесь нам не помогло ни тщательное удаление всех Int-ов, ни ClearFreeList, ни malloc_trim, ни gc.collect(2). Память осталась в распоряжение malloc-а и в ОС не вернулась.

PS. Примеры запускал под Python 2.7.3 Linux 2.6.32-33 i686. Если Вы можете проверить их под Windows, буду очень признателен.
В примере 2a в начале модуля была строка:

libc = ctypes.CDLL('libc.so.6')

Замените на msvcrt, делов-то.
Хм, не очень понятно, почему test_bad.py и test_ugly.py так себя ведут, вроде бы в реализации intobject'a есть освобождение промежуточных блоков, если их никто не держит.

Есть у меня подозрение, что это наведённый эффект от библиотеки memory_profile :) Доказать сейчас не возьмусь, но идея для проверки примерно такая — берём Ваш test_ugly.py, выкидываем декоратор, в каждой строчке втыкаем что-нибудь вроде time.sleep(0.1) (не втыкаем только в цикл).
Потребление памяти меряем внешним процессом.
Попробовал реализовать свою идею.

test_ugly.py:
import ctypes
import gc
import time

PAUSE = 1.0

def func():
    time.sleep(PAUSE)
    i = 0
    time.sleep(PAUSE)
    a = []
    time.sleep(PAUSE)
    while i < 10**5:
        a.append(i)
        i += 1
    time.sleep(PAUSE)
    del a
    time.sleep(PAUSE)
    del i
    time.sleep(PAUSE)
    ctypes.pythonapi.PyInt_ClearFreeList()    
    time.sleep(PAUSE)
    gc.collect(2)
    time.sleep(PAUSE)

if __name__ == '__main__':
    func()

Запускалка-измерялка b.py:
import psutil
import sys
import time

def main():
    proc = psutil.Popen([sys.executable, 'test_ugly.py'])
    stats = []
    while proc.poll() is None:
        # target is alive
        stats.append((time.time(), proc.get_memory_info().vms / 1024.0 / 1024))
        time.sleep(0.1)
    with open('result.txt', 'w') as out:
        out.write('%s\n' % '\n'.join('%s %.2f' % stat for stat in stats))
    
if __name__ == '__main__':
    main()


Построил график потребления виртуальной памяти (ActivePython 2.7.2 x86_64, Windows 7 x86_64):
image
По горизонтали — время, по вертикали — потребление памяти в мегабайтах.

Первый скачок — очевидно, инициализация самого интерпретатора. Второй — создание архива. Скачок вниз — освобождение. Освобождается, кстати, существенно больше, чем в Вашем примере, но явно не вся память.
Да, кстати, размер такого массива из 105 int'ов в случае моего питона занимает примерно 3 мегабайта (в смысле сумма размера list'a и размера всех int'ов), так что вроде как освобождается почти всё. Наверно, только сам объект a уходит в free list list'ов…

З.Ы. В сообщении выше вместо «второй — создание архива» читать «второй — создание массива» :)
Я так понимаю дело в реализации PyMalloc, а именно в том что он не хочет отдавать память, которая использовалась для хранения int/float обратно операционной системе после фактического уничтожения объектов, либо использовать ее для других целей, кроме как для хранения новых int/float.

То есть, если мы создадим много объектов (a = range(10**6)), то мы забираем 11.4mb у ОС на хранение int-ов и примерно 4mb на хранение списка. Если после этого удалим «a» (del a), то ОС вернется обратно 4mb, который высвободится из-под списка, но 11.4mb останется в распоряжение питона. Эту память может будет использовать только под новые int-ы/float.
Этот комментарий не верен. Intobject.c получает память напрямую через malloc и также ее освобождает. См. новый комментарий выше.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.