Optimize switch by strings.

[comm644]

Запишу из чата. переводить лень %)

Можно ли рассчитывать на оптимизацию ветвления по константным строкам?

(прикладная цель: повышение скорости рефлекшена для базы данных: при построении запроса я ТОЧНО знаю имя колонки и могу взять его из словаря константных строк )

пример:

class A{
        const nameA = "A";
        const nameB = "B";
        
        
        public int $a = 0;
        public int $b = 0;
        
        /**
        * @param mixed $value 
        */
        function setValue(string $name, $value ){
                switch( $name ) {
                case self::nameA: $this->a = (int)$value; break;
                case self::nameB: $this->b = (int)$value; break;
                }
        }
}

$a = new A;
$a->setValue( A::nameA, 10);
$a->setValue( A::nameB, 10);

Использование прямых строк в коде дают гибкость, но повышают вероятность ошибок времени исполнения, а не времени компиляции.

Поэтому правильный путь - использование строковых констант.

А с константами есть плюс: у нас есть адрес строки! Мы мы можем сделать ветвление сразу по адресу, если адреса не нашли то переходим к хешам. Это даст вычисление перехода за О(1) в лучшем сценарии. и О(длинны строки) в худшем

сейчаc транспилер герерит только хеши:

//16: switch( $name ) {
  {
    v$condition_on_switch$u2fae5d43c7d58a83_0 = f$strval (v$name);
    v$matched_with_one_case$u2fae5d43c7d58a83_0 = false;
    switch (v$condition_on_switch$u2fae5d43c7d58a83_0.as_string().hash()) {
      case 4112944471019094081:

время исполнения:

• через метод+ветвление: KPHP: 0.32, PHP: 8.2s
• по имени: KPHP: - , PHP: 1.6s
• прямой: kPHP: 0.02s PHP:1.23s

Доказательство

std::string не умеет оптимизировать память он копирует строки при присваивании %( Но если предавать const string по ссылке(они же не меняются да?) то схема работает!

time: 0.0222669

А так как в KPHP используется ссылочные константы, то есть возможность повышения скорости ветвления по строкам (а их в PHP программах много) при применении констант в 15 раз!!

#include <iostream>
#include <string>
#include <map>
#include <chrono>
double microtime(){
    return (double(std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count()) / double(1000000));
}

using namespace std;

class A
{
        public: long  a;
        public: long b;
        public: A(){ a = 0; b = 0; }
};

int main()
{
        const string nameA = "a";
        const string nameB = "b";
        
        //static const map , must initialized on first call.
        map<long, int > map; 
        map[(long)nameA.c_str()]= 1;
        map[(long)nameB.c_str()]= 2;
        
        const string &name = nameA; //use same string without copy

        A a;
        double tm = microtime();
        int nloops= 10000000;
        for( int i=0; i< nloops; ++i ){
                long ptr = (long)name.c_str();
                int idx= map[ ptr ];
                switch( idx ) {
                        case 1: a.a = i; break;
                        case 2: a.b = i; break;
                }
        }
        double done = microtime(); cout << (done - tm) << " " << a.a << endl;

        tm = microtime();
        for( int i=0; i< nloops+1; ++i ){
                a.a = i;
        }
        done = microtime(); cout << (done - tm) << " " << a.a << endl ;
}

[quasilyte]

Switching by addresses is not possible by a number of reasons.

More over, even if most strings are constant and addresses can be collected during the first switch execution, there still needs to be a second branch for strings that were created dynamically, so their addresses will not match the "case" clauses addresses. We don't have such a flag inside a string now. It's not worthwhile to add this new state that needs to be maintained just for this idea.

Here is how kphp compiles switches:

switch ($s) {
case 'foo':
  return 1;
case 'bar':
  return 2;
//...
}

=>

switch (hash(s)) {
case 8482137:
  if (s.equals("foo")) {
    return 1;
  }
case 248181274:
  if (s.equals("bar")) {
    return 2;
  }
//...
}

Hashing is fast. equals() is our == implementation, it works in O(n) in worst case.

As you see, switches are compiled like adhoc maps. We have precomputed hashes for cases and we check for equals() to defend against possible hash collisions (when we can get 248181274 hash from a string other than "bar", for instance). This is the only real difference from the map approach above, since hash is not unique and we need to do == in addition to hashing. In practice, case strings are quite short, comparing 10-20 chars sounds reasonable to me. For mismatching strings this comparison will fail due to the mismatching length in O(1).

There is, however, a way to make things a little bit faster in some corner cases. Like when we have short strings and we can compute a perfect hash which means no collisions. This way, we don't need equals() inside the case clause.