Моя программа python выполняется быстрее, чем моя java-версия одной и той же программы. Что дает?

Обновление: 2009-05-29

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

Уроки:

  • В моем примере ниже показана вставка примитивных int, но производственный код на самом деле хранит строки (мой плохой). Когда я исправил, что время выполнения python перешло с 2.8 секунд до 9.6. Таким образом, сразу с места в пути, ява была фактически быстрее при хранении объектов.

  • Но это не останавливается на достигнутом. Я выполнял java-программу следующим образом:

    java -Xmx1024m SpeedTest

Но если вы зададите начальный размер кучи следующим образом, вы получите огромное улучшение:

java -Xms1024m -Xmx1024m SpeedTest

Это простое изменение сократило время выполнения более чем на 50%. Итак, конечным результатом для моего SpeedTest является python 9,6 секунды. Java 6.5 секунд.

Оригинальный вопрос:

У меня был следующий код python:

import time
import sys

def main(args):    
    iterations = 10000000
    counts = set()
    startTime = time.time();    
    for i in range(0, iterations):
        counts.add(i)
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
    main(sys.argv)

И он выполнялся примерно на 3,3 секунды на моей машине, но я хотел ускорить его работу, поэтому решил запрограммировать его в java. Я предположил, что, поскольку java скомпилирован и обычно считается более быстрым, чем python, я бы увидел некоторые большие окупаемости.

Вот код java:

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        HashSet counts = new HashSet((2*iterations), 0.75f);

        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++)
        {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());
    }
}

Таким образом, этот Java-код выполняет в основном то же самое, что и код python. Но он выполнен за 8.3 секунды вместо 3.3.

Я извлек этот простой пример из реального примера, чтобы упростить вещи. Критическим элементом является то, что у меня есть (set или hashSet), который заканчивается множеством членов, подобных примеру.

Вот мои вопросы:

  • Почему моя реализация python быстрее, чем моя реализация Java?

  • Есть ли лучшая структура данных для использования, чем hashSet (java) для хранения уникальной коллекции?

  • Что бы сделать реализацию python быстрее?

  • Что бы сделать реализацию Java быстрее?

UPDATE:

Спасибо всем, кто внес свой вклад до сих пор. Позвольте мне добавить некоторые детали.

Я не включил свой производственный код, потому что он довольно сложный. И будет генерировать много отвлекающих факторов. Случай, который я излагаю выше, является наиболее упрощенным. Под этим я подразумеваю, что вызов java, по-видимому, намного медленнее, чем набор().

Java-реализация производственного кода также примерно в 2,5 - 3 раза медленнее, чем версия python, как и выше.

Я не беспокоюсь о перегреве или запуске vm. Я просто хочу сравнить код с моего startTime с моим итоговым временем. Пожалуйста, не беспокойтесь о других вопросах.

Я инициализировал hashset с более чем достаточным количеством ведер, чтобы ему никогда не приходилось перефразировать. (Я всегда буду знать заранее, сколько элементов будет содержать коллекция.) Полагаю, можно утверждать, что я должен был инициализировать его итерациями /0.75. Но если вы попробуете, вы увидите, что время выполнения не сильно повлияло.

Я установил Xmx1024m для тех, кому было любопытно (моя машина имеет 4 ГБ оперативной памяти).

Я использую java-версию: Java (TM) SE Runtime Environment (build 1.6.0_13-b03).

В производственной версии я сохраняю строку (2-15 символов) в hashSet, поэтому я не могу использовать примитивы, хотя это интересный случай.

Я запускаю код много, много раз. У меня очень высокая уверенность в том, что код python находится в 2,5 и 3 раза быстрее, чем Java-код.

Ответы

Ответ 1

На самом деле вы не тестируете Java и Python, вы тестируете java.util.HashSet с помощью встроенных в autoboxed целых чисел и Python с использованием собственных наборов и целочисленной обработки.

По-видимому, сторона Python в этом конкретном микрообъекте действительно быстрее.

Я попытался заменить HashSet на TIntHashSet из GNU trove и получил коэффициент ускорения между 3 и 4, что привело Java немного впереди Python.

Реальный вопрос: действительно ли ваш примерный код как представитель вашего кода приложения, как вы думаете. Запустили ли вы профилировщик и определили, что большая часть времени процессора тратится на то, чтобы разместить огромное количество ints в HashSet? Если нет, то пример не имеет значения. Даже если единственное отличие состоит в том, что ваш производственный код хранит другие объекты, кроме int, их создание и вычисление их хэш-кода могут легко доминировать над установленной установкой (и полностью разрушать преимущество Python при обработке ints специально), что делает весь этот вопрос бессмысленным.

Ответ 2

Я подозреваю, что Python сам использует значение integer как свой хэш, а реализация на основе хэш-таблицы набора использует это значение напрямую. Из комментариев в источник:

Это не обязательно плохо! Напротив, в таблице размера 2 ** i, принимая младшие биты i, поскольку индекс начальной таблицы чрезвычайно быстрый, и там вообще не являются столкновениями для индексов, проиндексированных непрерывным диапазоном int. То же самое примерно верно, когда клавиши являются "последовательными" строками. Итак, это дает лучшее, чем случайное поведение в общих случаях, и это очень желательно.

Этот микрообъект является одним из лучших для Python, потому что он приводит к точно нулевым хэш-коллизиям. Принимая во внимание, что если Javas HashSet перезаписывает ключи, он должен выполнить дополнительную работу, а также столкнется с гораздо худшими поведением при столкновении.

Если вы сохраняете диапазон (итерации) во временной переменной и выполняете random.shuffle на нем до цикла, время выполнения больше, чем на 2 раза медленнее, даже если перемещение и создание списка выполняется вне цикла.

Ответ 3

Как правило, мой опыт заключался в том, что программы python работают быстрее, чем java-программы, несмотря на то, что java - это немного более низкий уровень. Кстати, оба языка скомпилированы в байт-код (что то, что есть .pyc файл), вы можете думать о них как о типах .class файлов). Оба языка - это байт-код, интерпретируемый на виртуальной машине стека.

Вы ожидаете, что python будет медленнее в таких вещах, как, например, a.b. В java этот a.b будет разрешаться в разыменовании. С другой стороны, Python должен делать один или несколько запросов хеш-таблиц: проверять локальную область, проверять область модуля, проверять глобальную область, проверять встроенные функции.

С другой стороны, java, как известно, плохо работает при определенных операциях, таких как создание объектов (что, вероятно, является виновником в вашем примере) и сериализации.

Таким образом, нет простого ответа. Я бы не ожидал, что любой язык будет быстрее для всех примеров кода.

Исправление: несколько человек указали, что java не так уж плох при создании объекта. Итак, в вашем примере это что-то еще. Возможно, это автобоксирование этого дорогого, возможно, алгоритма хэширования по умолчанию для python в этом случае лучше. В моем практическом опыте, когда я переписываю java-код на python, я всегда вижу увеличение производительности, но это может быть так же, как из-за языка, так как это связано с переписыванием в целом, что приводит к повышению производительности.

Ответ 4

Другим возможным объяснением является то, что наборы в Python реализованы изначально в коде C, а HashSet в Java реализованы в самой Java. Таким образом, наборы в Python должны быть существенно быстрее.

Ответ 5

Я хотел бы развеять пару мифов, которые я видел в ответах:

Java компилируется, да, к байт-коду, но в конечном итоге к собственному коду в большинстве сред выполнения. Люди, которые говорят, что C по своей природе быстрее, не рассказывают всю историю, я мог бы сделать случай, когда байт-скомпилированные языки по своей природе быстрее, потому что компилятор JIT может создавать оптимизацию, зависящую от машины, которая недоступна компиляторам с опережением времени.

Несколько вещей, которые могут сделать различия:

  • Хэш-таблицы и наборы Python являются наиболее оптимизированными объектами в Python, а хеш-функция Python предназначена для возврата аналогичных результатов для аналогичных входов: хеширование целого числа возвращает целое число, гарантируя, что вы НИКОГДА не увидите столкновение в хеше таблица последовательных целых чисел в Python.
  • Вторичным эффектом вышеизложенного является то, что код Python будет иметь высокую локальность ссылки, поскольку вы будете получать доступ к хэш-таблице в последовательности.
  • Java делает некоторые причудливые бокс и распаковку целых чисел, когда вы добавляете их в коллекции. На стороне бонуса это делает арифметический путь быстрее в Java, чем Python (пока вы держитесь подальше от bignums), но с другой стороны это означает больше распределений, чем вы привыкли.

Ответ 6

Изменить: TreeSet может быть быстрее для реального использования, в зависимости от шаблонов распределения. Мои комментарии ниже относятся только к этому упрощенному сценарию. Однако я не считаю, что это будет иметь очень важное значение. Реальная проблема лежит в другом месте.

Несколько человек здесь рекомендовали заменить HashSet на TreeSet. Это звучит для меня очень странно, поскольку структура данных с временем ввода O (log n) быстрее, чем структура O (1), которая предопределяет достаточное количество ведер для хранения всех элементов.

Вот какой код для сравнения:

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        Set counts;

        System.out.println("HashSet:");
        counts = new HashSet((2*iterations), 0.75f);
        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++) {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());

        counts.clear();

        System.out.println("TreeSet:");
        counts = new TreeSet();
        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++) {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());
    }
}

И вот результат на моей машине:

$ java -Xmx1024M SpeedTest
HashSet:
TOTAL TIME = 4.436
10000000
TreeSet:
TOTAL TIME = 8.163
10000000

Несколько человек также утверждали, что бокс - это не проблема производительности, и создание объекта является недорогим. Хотя верно, что создание объекта происходит быстро, это определенно не так быстро, как примитивы:

import java.util.*;
class SpeedTest2
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        int[] primitive = new int[iterations];
        for (int i = 0; i < iterations; i++) {
            primitive[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        Integer[] boxed = new Integer[iterations];
        for (int i = 0; i < iterations; i++) {
            boxed[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
    }
}

Результат:

$ java -Xmx1024M SpeedTest2
primitives:
TOTAL TIME = 0.058
primitives:
TOTAL TIME = 1.402

Кроме того, создание большого количества объектов приводит к дополнительным накладным расходам от сборщика мусора. Это становится значительным, когда вы начинаете хранить в памяти десятки миллионов живых объектов.

Ответ 7

Я считаю, что такие тесты не имеют смысла. Я не решу проблемы, похожие на тестовые. Это не очень интересно.

Я бы скорее увидел решение для значимого решения линейной алгебры с использованием NumPy и JAMA. Может быть, я попробую и отчитаю результаты.

Ответ 8

Я не слишком хорошо знаком с python, но знаю, что HashSet не может содержать примитивы, поэтому, когда вы говорите counts.add(i) i, вы получаете автобокс в вызов new Integer(i). Это, вероятно, ваша проблема.

Если по какой-то причине вам действительно нужен "набор" целых чисел от 0 до некоторого большого n, его, вероятно, лучше всего объявить как "boolean [] set = new boolean [n]". Затем вы можете пройти через массив и пометить элементы, которые находятся в наборе как "истина", не налагая накладные расходы на создание n объектов-оболочек Integer. Если вы хотите пойти дальше, вы можете использовать байт [] размера n/8 и напрямую использовать отдельные биты. Или, может быть, BigInteger.

ИЗМЕНИТЬ

Прекратите голосовать за мой ответ. Это не правильно.

ИЗМЕНИТЬ

Нет, это неправильно. Я получаю сопоставимую производительность, если я делаю то, что предлагает этот вопрос, заполняя набор с помощью N целых чисел. если я заменил содержимое цикла for следующим:

    Integer[] ints = new Integer[N];
    for (int i = 0; i < N; ++i) {
        ints[i] = i;
    }

Затем это займет всего 2 секунды. Если вы вообще не храните Integer, это занимает менее 200 миллисов. Принудительное выделение объектов 10000000 Integer занимает некоторое время, но похоже, что большая часть времени проводится внутри операции ввода HashSet.

Ответ 9

Здесь есть несколько вопросов, которые я хотел бы объединить.

Сначала, если это программа, которую вы собираетесь запускать только один раз, имеет ли значение, что требуется несколько секунд?

Во-вторых, это всего лишь один микроцентриф. Microbenchmarks бессмысленны для сравнения производительности.

В автозапуске есть ряд проблем.

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

Если вы не установили -Xms, вы можете запустить GC только для изменения размера кучи. Возможно также, чтобы куча была должным образом настроена в начале.

Верно, что Java начинает интерпретировать, а затем компилирует. Около 1500 итераций для Sun client [C1] Точка доступа и 10 000 для сервера [C2]. Сервер Hotspot даст вам лучшую производительность в конечном итоге, но возьмет больше памяти. Мы можем видеть сервер использования Hotspot клиента для очень часто исполняемого кода для лучшего из обоих миров. Однако обычно это не вопрос секунд.

Самое главное, что вы можете создавать два объекта на итерацию. Для большинства кода вы не будете создавать эти крошечные объекты для такой части исполнения. TreeSet может быть лучше по количеству очков объектов, при этом 6u14 и Harmony становятся еще лучше.

Возможно, Python может выиграть, сохранив мелкие целые объекты в ссылках вместо фактического объекта. Это, несомненно, хорошая оптимизация.

Проблема с множеством эталонных тестов заключается в том, что вы смешиваете много разных кодов в одном методе. Вы не будете писать код, о котором вы так беспокоились, не так ли? Итак, почему вы пытаетесь выполнить тест производительности, который не похож на код, который вы действительно хотите запустить быстро?

Лучшая структура данных: что-то вроде BitSet показало бы смысл (хотя на нем есть синхронизация, которая может или не может повлиять на производительность).

Ответ 10

Вам нужно запустить его несколько раз, чтобы получить реальную идею о том, "как быстро" каждый работает. Время запуска JVM [для одного] добавляет к единому времени выполнения версии Java.

Вы также создаете HashSet с большой начальной емкостью, что означает, что HashMap будет создан с таким количеством доступных слотов, в отличие от Python, где вы создаете базовый набор. Трудно сказать, будет ли это мешать, поскольку, когда ваш HashSet растет, ему придется перераспределять сохраненные объекты.

Ответ 11

Используете ли вы флаг -server с jvm? Вы не можете проверить производительность без него. (Вы также должны разогреть jvm перед выполнением теста.)

Кроме того, вы, вероятно, захотите использовать TreeSet<Integer>. В конечном итоге HashSet будет медленнее.

И какой jvm вы используете? Надеюсь, что самое новое.

ИЗМЕНИТЬ

Когда я говорю использование TreeSet, я имею в виду, в общем, не для этого теста. TreeSet обрабатывает проблему реального мира без четкого хэширования объектов. Если вы получаете слишком много объектов в одном ящике в HashSet, вы будете выполнять около O (n).

Ответ 12

Если вы действительно хотите хранить примитивные типы в наборе и выполнять тяжелую работу над этим, сверните свой собственный набор на Java. Родовые классы недостаточно быстры для научных вычислений.

Как упоминает Ants Aasma, Python обходит хэширование и использует целое число напрямую. Java создает объект Integer (autoboxing), а затем передает его объекту (в вашей реализации). Этот объект также должен быть хэширован для использования в хэш-наборе.

Для веселого сравнения попробуйте следующее:

Java

import java.util.HashSet;
class SpeedTest
{ 
  public static class Element {
    private int m_i;
    public Element(int i) {
      m_i = i;
    }
  }

  public static void main(String[] args)
  {        
    long startTime;
    long totalTime;
    int iterations = 1000000;
    HashSet<Element> counts = new HashSet<Element>((int)(2*iterations), 0.75f);

    startTime = System.currentTimeMillis();
    for(int i=0; i<iterations; ++i)
    {
      counts.add(new Element(i));
    }
    totalTime = System.currentTimeMillis() - startTime;
    System.out.println("TOTAL TIME = "+( totalTime/1000f) );
    System.out.println(counts.size());
  }
}

Результаты:

$java SpeedTest
TOTAL TIME = 3.028
1000000

$java -Xmx1G -Xms1G SpeedTest
TOTAL TIME = 0.578
1000000

Python

#!/usr/bin/python
import time
import sys

class Element(object):
  def __init__(self, i):
    self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    startTime = time.time();    
    for i in range(0, iterations):
        counts.add(Element(i))
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)


if __name__ == "__main__":
  main(sys.argv)

Результаты:

$./speedtest.py 
total time = 20.6943161488
1000000

Как это для "python быстрее, чем java"?

Ответ 13

Сколько памяти вы начали с JVM? Это зависит? Когда я запускаю JVM с вашей программой с 1 Gig RAM:

$ java -Xmx1024M -Xms1024M -classpath . SpeedTest 
TOTAL TIME = 5.682
10000000
$ python speedtest.py 
total time = 4.48310899734
10000000

Если я запускаю JVM с меньшим объемом памяти, это занимает больше времени... значительно дольше:

$ java -Xmx768M -Xms768M -classpath . SpeedTest 
TOTAL TIME = 6.706
10000000
$ java -Xmx600M -Xms600M -classpath . SpeedTest 
TOTAL TIME = 14.086
10000000

Я думаю, что HashSet является узким местом производительности в данном конкретном случае. Если я заменил HashSet на LinkedList, программа будет значительно быстрее.

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

Ответ 14

Просто удар в темноте здесь, но некоторые оптимизации, которые Python делает с этой Java, вероятно, не таковы:

  • Вызов range() в Python создает все 10000000 целых объектов одновременно, в оптимизированном C-коде. Java должна создавать объект Integer на каждой итерации, что может быть медленнее.
  • В Python ints неизменяемы, поэтому вы можете просто сохранить ссылку на глобальную "42", например, вместо выделения слота для объекта. Я не уверен, как сравниваются объекты Java Integer с ядром.
  • Многие из встроенных алгоритмов Python и структуры данных довольно сильно оптимизированы для особых случаев. Например, хеш-функция для целых чисел - это просто функция тождества. Если Java использует более "умную" хеш-функцию, это может немного замедлить работу. Если большая часть вашего времени будет потрачена на код структуры данных, я бы не удивился, увидев, что Python избили Java, учитывая объем усилий, которые были потрачены на протяжении многих лет, настраивая реализацию Python C.

Ответ 15

Несколько изменений для более быстрого Python.

#!/usr/bin/python
import time
import sys

import psyco                 #<<<<  
psyco.full()

class Element(object):
    __slots__=["num"]        #<<<<
    def __init__(self, i):
        self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    startTime = time.time();
    for i in xrange(0, iterations):
        counts.add(Element(i))
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
  main(sys.argv)

Перед

(env)~$ python speedTest.py
total time = 8.82906794548
1000000

После

(env)~$ python speedTest.py
total time = 2.44039201736
1000000

Теперь хороший старый обман и...

#!/usr/bin/python
import time
import sys
import psyco

psyco.full()

class Element(object):
    __slots__=["num"]
    def __init__(self, i):
        self.num = i

def main(args):    
    iterations = 1000000
    counts = set()
    elements = [Element(i) for i in range(0, iterations)]
    startTime = time.time();
    for e in elements:
        counts.add(e)
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
  main(sys.argv)

(env)~$ python speedTest.py
total time = 0.526521921158
1000000

Ответ 16

Я согласен с Гэндалом относительно времени запуска. Кроме того, вы выделяете огромный HashSet, который совсем не похож на ваш код на Python. Я создаю изображение, если вы положите его под профилировщик, там будет потрачен хороший кусок времени. Кроме того, вставка новых элементов действительно будет медленной с этим размером. Я бы посмотрел на TreeSet, как было предложено.

Ответ 17

Самая большая проблема, вероятно, в том, что показатели данного кода время на стене - что ваши часы измеряют - но что следует измерять для сравнения времени выполнения кода время процесса - время, затрачиваемое процессором на выполнение этого конкретного кода, а не другие задачи.

Ответ 18

Вы можете сделать Java microbenchamrk намного быстрее, добавив просто немного лишнее.

    HashSet counts = new HashSet((2*iterations), 0.75f);

становится

    HashSet counts = new HashSet((2*iterations), 0.75f) {
        @Override public boolean add(Object element) { return false; }
    };

Простой, быстрый и получает тот же результат.

Ответ 19

Возможно, вам захочется узнать, можете ли вы "подготовить" компилятор JIT к компиляции раздела кода, который вас интересует, возможно, запустив его как функцию один раз заранее и спящий короткий пароль. Это может позволить JVM скомпилировать функцию с помощью собственного кода.

Ответ 20

Ну, если вы собираетесь настраивать программу Java, вы можете также настроить программу Python.

>>> import timeit
>>> timeit.Timer('x = set()\nfor i in range(10000000):\n    x.add(i)').repeat(3, 1)
[2.1174559593200684, 2.0019571781158447, 1.9973630905151367]
>>> timeit.Timer('x = set()\nfor i in xrange(10000000):\n    x.add(i)').repeat(3, 1)
[1.8742368221282959, 1.8714439868927002, 1.869229793548584]
>>> timeit.Timer('x = set(xrange(10000000))').repeat(3, 1)
[0.74582195281982422, 0.73061800003051758, 0.73396801948547363]

Просто использование xrange делает его на 8% быстрее на моей машине. И выражение set(xrange(10000000)) строит точно такой же набор, но в 2,5 раза быстрее (с 1,87 секунды до 0,74).

Мне нравится, как настройка программы Python делает ее более короткой.:) Но Java может сделать тот же трюк. Как известно, если вам нужен плотный набор маленьких чисел на Java, вы не используете хеш-таблицу. Вы используете java.util.BitSet!

BitSet bits = new BitSet(iterations);

startTime = System.currentTimeMillis();
bits.set(0, iterations, true);
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(bits.cardinality());

Это должно быть довольно быстро. К сожалению, у меня нет времени проверить его прямо сейчас.