Сравнение производительности конкатенации неизменных строк между Java и Python

Question

ОБНОВЛЕНИЯ: большое спасибо Гейбу и Гленну за подробное объяснение.Тест написан не для сравнения языков, а для изучения технологий оптимизации виртуальных машин.

Я провел простой тест, чтобы понять производительность конкатенации строк между Java и Python.

Тест является целевым для неизменяемого объекта / типа String по умолчанию на обоих языках.Поэтому я не использую StringBuilder / StringBuffer в тесте Java.

Тест просто добавляет строки по 100 тыс. Раз.Java потребляет ~ 32 секунды для завершения, в то время как Python использует только ~ 13 секунд для строки Unicode и 0,042 секунды для строки не Unicode.

Я немного удивлен результатами.Я думал, что Java должна быть быстрее, чем Python.Какую технологию оптимизации использует Python для достижения лучшей производительности?Или объект String слишком тяжелый в Java?

ОС: Ubuntu 10.04 x64 JDK: Sun 1.6.0_21 Python: 2.6.5

Тест Java действительно использовал -Xms1024m для минимизации операций GC.

Java-код:

public class StringConcateTest {
public static void test(int n) {
    long start = System.currentTimeMillis();
    String a = "";
    for (int i = 0; i < n; i++) {
        a = a.concat(String.valueOf(i));
    }
    long end = System.currentTimeMillis();
    System.out.println(a.length() + ", time:" + (end - start));
}

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        test(1000 * 100);           
    }
}

}

Python-код:

import time
def f(n):
    start = time.time()
    a = u'' #remove u to use non Unicode string
    for i in xrange(n):
        a = a + str(i)
    print len(a), 'time', (time.time() - start)*1000.0
for j in xrange(10):
    f(1000 * 100)

Answer 1

@ Ответ Гейба верен, но его нужно показывать четко, а не выдвигать гипотезы.

CPython (и, вероятно, только CPython) добавляет строку на месте, когда это возможно.Есть ограничения на то, когда он может сделать это.

Во-первых, он не может сделать это для интернированных строк.Вот почему вы никогда не увидите этого, если протестируете с a = "testing"; a = a + "testing", потому что назначение строкового литерала приводит к интернированной строке.Вы должны создать строку динамически, как этот код делает с str(12345).(Это не является большим ограничением; после того, как вы добавите этот способ один раз, result будет неинтернизированной строкой, поэтому, если вы добавляете строковые литералы в цикл, это произойдет только в первый раз.)

Во-вторых, Python 2.x делает это только для str, а не unicode.Python 3.x делает это для строк Unicode.Это странно: разница в производительности - разница в сложности .Это препятствует использованию строк Unicode в 2.x, когда они должны поощрять его к переходу на 3.x.

И, наконец, не может быть никаких других ссылок на строку.

>>> a = str(12345)
>>> id(a)
3082418720
>>> a += str(67890)
>>> id(a)
3082418720

Это объясняет, почему не-Unicode версия намного быстрее в вашем тесте, чем Unicode-версия.

Фактический код для этого string_concatenate в Python/ceval.c и работает для обоих s1 = s1 + s2и s1 += s2.Функция _PyString_Resize в Objects/stringobject.c также прямо говорит: Следующая функция нарушает представление о том, что строки неизменны .Смотри также http://bugs.python.org/issue980695.

Answer 2

Я предполагаю, что Python просто делает realloc в строке, а не создает новый с копией старого.Поскольку realloc не занимает много времени, когда после выделения достаточно свободного места, оно выполняется очень быстро.

Так почему же Python может вызывать realloc, а Java - нет?Сборщик мусора в Python использует подсчет ссылок, поэтому он может сказать, что никто другой не использует строку, и не имеет значения, если строка изменится.Сборщик мусора в Java не поддерживает подсчет ссылок, поэтому он не может определить, существует ли какая-либо другая ссылка на строку, то есть у него нет другого выбора, кроме как создавать новую копию строки при каждой конкатенации.

РЕДАКТИРОВАТЬ: Хотя я не знаю, что Python действительно вызывает realloc на concat, вот комментарий для _PyString_Resize в stringobject.c, указывающий, почему он может:

       The following function breaks the notion that strings are immutable:
       it changes the size of a string.  We get away with this only if there
       is only one module referencing the object.  You can also think of it
       as creating a new string object and destroying the old one, only
       more efficiently.  In any case, don't use this if the string may
       already be known to some other part of the code...

Answer 3

Я не думаю, что ваш тест много значит, так как Java и Python обрабатывают строки по-разному (я не эксперт в Python, но я знаю свой путь в Java). StringBuilders / Buffers существует по причине в Java. Разработчики языка не сделали какой-либо более эффективной системы управления / манипулирования памятью именно по этой причине: существуют другие инструменты, кроме объекта «String», для выполнения таких манипуляций, и они ожидают, что вы будете использовать их при кодировании.

Когда вы делаете вещи так, как они должны быть выполнены в Java, вы будете удивлены, насколько быстро работает платформа ... Но я должен признать, что меня впечатлила производительность некоторых приложений Python, которые я попробовал недавно.

Answer 4

Я запустил код Java с StringBuilder вместо String и увидел среднее время окончания 10 мс (максимум 34 мс, низкий 5 мс).

Что касается кода Python, используя «Метод 6» здесь (считается самым быстрым методом), я смог достичь в среднем 84 мс (высокий 91 мс, низкий 81 мс), используя строки в юникоде.Использование не-юникодных строк уменьшило эти числа на ~ 25 мс.

Таким образом, на основании этих крайне ненаучных тестов можно сказать, что при использовании самого быстрого из доступных методов для конкатенации строк Java примерно на порядок быстрее, чемPython.

Но я все еще <3 Python;) </p>

Answer 5

Я точно не знаю ответа. Но вот несколько мыслей. Во-первых, Java внутренне хранит строки как char [] массивы, содержащие кодировку строки UTF-16. Это означает, что каждый символ в строках занимает как минимум два байта. Так что, просто с точки зрения необработанного хранилища, Java пришлось бы копировать примерно вдвое больше данных, чем строки Python. Поэтому лучше всего тестировать Python-юникодные строки, поскольку они аналогично способны . Возможно, Python хранит строки Unicode как байты в кодировке UTF-8. В этом случае, если все, что вы храните в этих символах, - это символы ASCII, то снова у вас будет Java, использующий вдвое больше места и, следовательно, выполняющий вдвое больше копирования. Чтобы получить лучшее сравнение, вам следует объединить строки, содержащие более интересные символы, для которых в кодировке UTF-8 требуется два или более байтов.