Быстрый «хеш» со статичным набором ключей?

Гугли «perfect hashing».

внутри этот метод проверяет, есть ли соотв функция KEY_{NAME}

Вот это отображение строки в функцию/число и будет медленным. Хотите максимально быстро - используйте enum и товарищей - те перекладывают всё, что может быть медленным, на compile time.

also посмотреть на Class::XSAccessor::Array

enum же и создаёт те же самые use constant-подобные функции, возвращающие число:

 use enum qw(
      :Months_=0 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
      :Days_=0   Sun Mon Tue Wed Thu Fri Sat
      :LC_=0     Sec Min Hour MDay Mon Year WDay YDay Isdst
  );

  if ((localtime)[LC_Mon] == Months_Jan) {
      print "It's January!\n";
  }

LC_Mon -здесь - это функция, её можно и как LC_Mon() вызвать.

also посмотреть на Class::XSAccessor::Array

Спасибо, уже смотрю.

Да, но отображать строку обратно в use constant-подобную функцию придётся через хэш, а это для Вас медленно. А в стартовом сообщении написано, что произвольные ключи нужны.

Почему через хеш?

Это же просто функция.

perl -e 'use constant R=>"hello\n"; my $x="R"; print $x->()'
hello

И так тоже:

perl -e 'use constant R=>"hello\n"; $x="R"; my $l=\&{$x}; print ref($l)." => ".$l->()'
CODE => hello

И даже так:

use strict;
use constant R=>"hello\n";
no strict "refs";
my $x="R"; *{__PACKAGE__."::$x"} = sub { "bye\n" };
my $l = \&{$x};
print ref($l)." => ".$l->()

Output:

Constant subroutine main::R redefined at -e line 1.
Prototype mismatch: sub main::R () vs none at -e line 1.
CODE => bye

Охренеть, дайте два...

$ perl -e 'use strict; use 5.16.1; use constant R=>"hello\n"; no strict "refs"; my $x="R"; *{__PACKAGE__."::$x"}=sub () { "bye\n" }; print R; my $l=\&{$x}; print ref($l)." => ".$l->()'
Constant subroutine main::R redefined at -e line 1.
hello
CODE => bye

Symbolic reference? Это не очень-то безопасно и наверняка медленнее, чем hard references. Внутри оно всё равно должно как-то отобразить строку (имя функции) в CODE, то есть, найти её в stash. То есть, сделать hash lookup, хотя бы и во внутреннем хэше.

Вызов же функции не из строки, а напрямую (use enum whatever; whatever()) компилируется один раз сразу в вызов CODE.

В https://github.com/rurban/Perfect-Hash есть XS для CMPH

Эта ж Class::Struct, не?

Насколько я помню, начиная с какой то версии перла была проведена оптимизация случая, bless {key => $val, ...}, когда набор ключей при создании объекта был константным и не менялся в процессе работы — доступ к хешу ускоряется. А так он ровно в два раза тормознее массива.

Ровно в 2 раза независимо от количества ключей в хеше? Тогда это O(1). Однако, существуют коллизии, их количество зависит от количества ключей, а значит, алгоритмическая сложность хеша зависит от n, а как именно - зависит от алгоритма хеширования..

Посмотрел я на это, но так и не понял, как пользоваться. Какие-то компиляции gcc с оптимизацией под sse4... О чём это, кто все эти люди? :) Но посмотрю обязательно ещё, должно наступить просветление.

Ровно в 2 раза независимо от количества ключей в хеше?

Практически, да. Дело в том, что хеш перестраивается по мере роста, увеличивается количество корзин. Я экспериментировал с этим, колллизии редкость, как правило в одной корзине не более чем один элемент.

$ perl -le 'for($_=1; $_ < 1000; $_ += $_) { $h{$_}=$_+2 for (1..$_); print "$_: @{[scalar %h]}"}'
1: 1/8
2: 2/8
4: 3/8
8: 5/16
16: 11/32
32: 27/64
64: 54/128
128: 99/256
256: 200/512
512: 397/1024

формат:

число: элементов/корзин

Посмотрел я на это, но так и не понял, как пользоваться. Какие-то компиляции gcc с оптимизацией под sse4... О чём это, кто все эти люди? :) Но посмотрю обязательно ещё, должно наступить просветление.

Краткое содержание без претензий на полноту

1) Есть библиотека cmph (C Minimal Perfect Hash), которая позволяет для заданного в рантайме набора строк сделать совершенную хэш-функцию (т.е. без коллизий), по совместительству являющуюся минимальной (отображает N строк в числа от 0 до N-1). Это позволяет вместо любых хэш-таблиц использовать массивы, сгенерил функцию и пользуйся

2) Есть некий (похоже не вполне доделанный) модуль Perfect::Hash, автор которого задался целью поддержать кучу генераторов совершенных хэшей, а заодно и узнать, какой из них круче. Вот к этой части и относится цирк с конями и sse4. Однако единственный известный мне на вскидку генератор, работающий в рантайме - CMPH, так что можно было бы выдрать его поддержку из этого модуля и юзать у себя

Есть другие генераторы, gperf например, но их хорошо юзать когда у тебя набор ключей более менее постоянный, так что можно заранее сгенерить хэш-функцию и загрузить к себе в скрипт. Насколько я понимаю, именно этого хотел добиться автор Perfect::Hash, автоматически компилить XS-модули для заданного набора ключей.

Лучше бы сделал по-рабочекрестьянски обертку для CMPH, имхо

https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_func...

http://cmph.sourceforge.net/