Оптимизация компилятора в кейсе - PullRequest
Новая
       6

Оптимизация компилятора в кейсе

2 голосов
/ 02 января 2011

Я хотел бы расширить свои знания и навыки в написании компиляторов, особенно по оптимизации.Я хотел бы знать, какие оптимизации доступны для case-операторов с выражением case строкового типа.Например, в Object Pascal: 

ReadLn(s);
case s of
  'abc','def': ...;
  'xyz'      : ...;
  otherwise    ...;
end;

в Free Pascal это переводится в последующие вызовы AnsiCompareText.А как насчет других языковых реализаций?Я знаю, по крайней мере, PHP, Nimrod и Octave поддерживают это.

Ответы [ 2 ]

0 голосов
/ 12 апреля 2012

В C нет эквивалента "case" для массивов символов (строк), но это может быть выполнено до некоторой степени с помощью макроса сдвига битов и регистра переключателя 

#define FIVE_CHARS(c1,c2,c3,c4,c5)  (((((((((c5)<<7)|(c4))<<6)|(c3))<<6)|(c2))<<6)|(c1))

while (argc-->0){
  switch ( FIVE_CHARS(argv[argc][0],argv[argc][1],argv[argc][2],argv[argc][3],argv[argc][4]) ){
     case FIVE_CHARS('-','h','e','l','p')  :
     case FIVE_CHARS('-','-','h','e','l')   :
     case FIVE_CHARS('-','h','\0','\0','\0')   :
     case FIVE_CHARS('-','?','\0','\0','\0')   :
       usage();
     break;
     case FIVE_CHARS('-','a','r','g','1')   :
       setflag1();
     break;
     default:
       assert("Argument not supported");
  }
}

Компилятор может скомпилировать это каксерия if с небольшим количеством сравнений или таблица переходов с большим числом.Это может обеспечить значительное улучшение как размера кода, так и скорости, поскольку большинство битовых сдвигов (те, что в операторах case) выполняются во время компиляции, а не во время выполнения, оставшаяся операция сдвига битов (та, что в коммутаторе) является относительно дешевой итребуется только один раз для одиночного сравнения (по сути, сводя на нет необходимость ставить самые распространенные пути первыми) ... для случаев с совпадением пяти символов вы можете добавить дополнительный переключатель для необычного символа / символов или просто использовать strcmp ()... все же лучше использовать в некоторых случаях только strcmp, а не огромное вложенное дерево if strcmp () {} else if strcmp () {} else ...

0 голосов
/ 04 февраля 2011

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

Если бы я писал свой собственный компилятор и столкнулся с оператором case, подобным приведенному выше, я, вероятно, попытался бы отсортировать сравнения и выполнить двоичный файлпоиск, чтобы определить, какой путь выбрать.Мы надеемся, что это немного улучшит худший вариант.

...