Чего мне не хватает в FreePascal

[devels]

Если SAVE_INTS - массив shortstring (а string[4] - это shortstring), то в они в цикле преобразуются в ansistring, причем два раза - один при добавлении, другой при чтении...
Но вообще 3.5 секунды на, грубо говоря, цикл из 2000 итераций - это какая-то совсем уж хрень. Тут нужно разбираться.

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

Поставил IntToStr, скорость такая же, ну короче - это мили-мили, я делал тесты shortstring -> string у меня на скорость влиял, за счет кеширования я увеличивал в fpc скорость выполнения этой функции в 3 раза, там тоже массив из shortstring.

Но я кстати скажу, в делфи тоже будет не быстрее чем в пхп. Так что здесь не только в менеджере памяти дело, возможно надо как-то улучшать реализацию хеш-таблицы. У меня получалось увеличить скорость, она приближалась к php, но если отбросить интерпретацию все равно отставала по скорости.


И там не 2000 итераций, а 2000 * 1000 это 2 млн.

Ради прикола протестил тот код у себя в скрипт-движке, даже у меня он выполняется за 3700 mlsec, и это же жесть, практически такая же скорость как у fpc, только у меня своя хеш-таблица, расходы на интерпритацию примерно 1000 млсек, в итогде примерно на таблицу тратится 2700 mlsec.

[Sergei I. Gorelkin]

А ось какая, винда или линукс?

[Шурик Сетевой]

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

[devels]

Операционка Win XP 32.

Хеш функция у меня самая простая и максимально быстрая, быстрее сделать нереально:
По-моему в FPC тоже простая функция.

Код: Выделить всё

function HashTable_Func(const key: AnsiString): Cardinal;
const Seed = 31; (* 31 131 1313 13131 131313 etc... *)
var
  i,len: Cardinal;
begin
  Result := 0;
  len := Length(Key);
  for i := 1 to Len do
    Result := (Result * Seed) + Byte(Key[i]);

  Result := Result and $7FFFFFFF;
end;


[Sergei I. Gorelkin]

Да, действительно windows. Что-то я совсем нюх потерял, "uses windows" в упор не вижу

Вот примерный расклад для данного теста (в linux, но сути это не меняет):

Код: Выделить всё

   55,139,126  *  /project1.pp:main
        1,412  >   fpc_dynarray_setlength (1x)
           12  >   fpc_setjmp (1x)
           21  >   fpc_popaddrstack (1x)
  383,677,293  >   fpc_shortstr_to_ansistr (2004002x)
  480,802,322  >   CONTNRS_TFPSTRINGHASHTABLE_$__GETDATA$ANSISTRING$$ANSISTRING (1002001x)
  205,321,116  >   fpc_shortstr_concat (2004002x)
           30  >   fpc_pushexceptaddr (1x)
   10,542,169  >   CONTNRS_TFPCUSTOMHASHTABLE_$__CREATE$$TFPCUSTOMHASHTABLE (1x)
       52,365  >   SYSTEM_DO_EXIT (1x)
  220,730,378  >   fpc_ansistr_decr_ref (4009007x)
      527,825  >   SYSUTILS_INTTOSTR$LONGINT$$ANSISTRING (1001x)
       97,212  >   fpc_initializeunits (1x)
       59,515  >   fpc_ansistr_to_shortstr (1001x)
24,406,199,607  >   CONTNRS_TFPCUSTOMHASHTABLE_$__CLEAR (1001x)
  989,597,535  >   CONTNRS_TFPSTRINGHASHTABLE_$__ADD$ANSISTRING$ANSISTRING (1002001x)
   16,032,016  >   fpc_ansistr_incr_ref (1002001x)


Грабли оказываются вовсе не там, где их ждали...

[bw]

Вот примерный расклад для данного теста...

А как мне такую же картинку сделать?

..bw

[devels]

Да, действительно windows. Что-то я совсем нюх потерял, "uses windows" в упор не вижу

Вот примерный расклад для данного теста (в linux, но сути это не меняет):

Код: Выделить всё

24,406,199,607  >   CONTNRS_TFPCUSTOMHASHTABLE_$__CLEAR (1001x)
  989,597,535  >   CONTNRS_TFPSTRINGHASHTABLE_$__ADD$ANSISTRING$ANSISTRING (1002001x)


Грабли оказываются вовсе не там, где их ждали...

Я так понимаю Clear тормознутый?

[vada]

Посмотрел на реализацию TFPStringHashTable...
Тупо в лоб без изысков. Более медленный HashTable вариант создать непросто.
Найду время, перепишу. Вернее, с JAVA срисую.

[devels]

Вот реализация побыстрее:

http://code.google.com/p/dwscript/sourc ... tables.pas

Только хеш-функция там слишком сложная, и элементы хеш-таблицы я бы сделал рекордами, а не объектами, и всякие методы Equals заменил бы на че нить побыстрее, а то из-за универсальности это сказывается на скорости выполнения.

[Sergei I. Gorelkin]

А как мне такую же картинку сделать?

Это valgrind. Установив его в линуксе, компилируем программу с -gl (чтобы видеть номера строк), потом

Код: Выделить всё

valgrind --tool=callgrind <имя программы>
(оно печатает всякую хрень, но каждая строка начинается с цифры. Цифру запоминаем)
callgrind_annotate --tree=calling callgrind.out.<цифра>


Еще можно установить разную гуйню вроде alleyoop, и любоваться на окошки.

Я так понимаю Clear тормознутый?

Он самый.

Посмотрел на реализацию TFPStringHashTable...Тупо в лоб без изысков. Более медленный HashTable вариант создать непросто.Найду время, перепишу. Вернее, с JAVA срисую.

В том же модуле contnrs есть класс TFPHashList, копия которого используется в самом компиляторе и в каких-то тормозах не замечена. Единственное, у него ключи типа shortstring, а не ansistring. Возможно, позаимствовать нужные решения из него окажется проще.

[devels]

В том же модуле contnrs есть класс TFPHashList, копия которого используется в самом компиляторе и в каких-то тормозах не замечена. Единственное, у него ключи типа shortstring, а не ansistring. Возможно, позаимствовать нужные решения из него окажется проще.

Ну блин 256 символов часто мало, например путь к программе может быть куда больше. Но протестил класс TFPHashList, он отрабатывается за 300 млсек, это получается в 10 раз быстрее, а то и более...

Дело в том, что для цепочки в TFPDataHashList и подобные - используется не связанный список, а тупо TObjectList (т.е. блин лишние расходы на создание целого ненужного объекта), когда можно хранить цепочку, в виде связанных рекордов, и вдобавок в одну лишь сторону.

Код: Выделить всё

type
   PTableItem = ^TTableItem;
   TTableItem = record
       key: AnsiString; 
       hashCode: LongWord;
       next: PHashItem;


Короче, надо переписывать TFPHashTable для AnsiString ключей, там вроде достаточно добавить параметр длина-ключа и немного магии, чтобы переделать класс. Вот там как раз и на цепочках сделано.

[vada]

Посмотрел на реализацию TFPStringHashTable...Тупо в лоб без изысков. Более медленный HashTable вариант создать непросто.Найду время, перепишу. Вернее, с JAVA срисую.

В том же модуле contnrs есть класс TFPHashList, копия которого используется в самом компиляторе и в каких-то тормозах не замечена. Единственное, у него ключи типа shortstring, а не ansistring. Возможно, позаимствовать нужные решения из него окажется проще.

В JAVA реализовано все гараздо вкуснее. Там каждый объект имеет свой Hash код (Integer). Напримар, если сравниваются две строки на равенство, на самом деле, сравниваются их Hash-и. Поэтому быстро.
Вопервых, сравнение двух Integer гораздо быстрее чем двух String.
Вовторых, в HashTable ключи собираются в двоичное дерево. Поиск по дереву побыстрее прямого перебора в разы.

ЗЫ. Это на пальцах. На самом деле HashTable в JAVA посложнее будет. Это чума как он быстро работает!!!

[perlpunk]

http://www.freepascal.org/docs-html/fcl ... glist.html
THashedStringList - А что скажете про эту реализацию?

Если в java такой крутой функционал HashTables почему бы не своровать оттуда исходники и реализовать на их основе в fpc?

[devels]

Посмотрел на реализацию TFPStringHashTable...Тупо в лоб без изысков. Более медленный HashTable вариант создать непросто.Найду время, перепишу. Вернее, с JAVA срисую.

В том же модуле contnrs есть класс TFPHashList, копия которого используется в самом компиляторе и в каких-то тормозах не замечена. Единственное, у него ключи типа shortstring, а не ansistring. Возможно, позаимствовать нужные решения из него окажется проще.

В JAVA реализовано все гараздо вкуснее. Там каждый объект имеет свой Hash код (Integer). Напримар, если сравниваются две строки на равенство, на самом деле, сравниваются их Hash-и. Поэтому быстро.
Вопервых, сравнение двух Integer гораздо быстрее чем двух String.
Вовторых, в HashTable ключи собираются в двоичное дерево. Поиск по дереву побыстрее прямого перебора в разы.

ЗЫ. Это на пальцах. На самом деле HashTable в JAVA посложнее будет. Это чума как он быстро работает!!!

А что ты думаешь, в какой-то хеш-таблице сравниваются строки? Они там сравниваются один раз в конце, чтобы избежать коллизий, а так сравниваются не строки а их хеш-коды. И кстати там есть параметр - наполненность, цепочки не такие длинные, чтобы для них создавать дерево для поиска, в них то максимум элементов 20-30 по самим пессимистическим расчетам.

[vada]

Там сравнивается не только строка, но хэш, длинна строки, последний символ строки. Чего бы еще сравнить?..Мммм... Можно контрольную сумму еще посчитать. Упущение