программистское

[avva]

Все-таки забавно, насколько использование виртуальных методов убивает скорость. Prefetch queue - наше все.

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

Comments

[nine_k]

На 100% нельзя, но обычно столько и не нужно.
У нас ведь JIT-компилятор, он же по совместительству и профайлер. Поэтому он может заметить, что в часто вызываемом цикле, который проходит по ряду объектов, в 95% случаев встречаются вызовы виртуального метода f() для объектов класса A. Другие тоже могут попасться, но они редки.
Поэтому JIT может заменить цикл таким эквивалентным кодом:

for x in [whatever]:
 if x instaceof A:
  тут inline код A.f()
 else:
  тут вызов виртуальной x.f()

В результате заинлайнен будет самый частый из виртуальных методов, что в 95% случаев будет эквивалентно невиртуальному варианту (со всеми плюсами prefetch queue, которая тоже не глупая и переходы предсказывает). В оставшихся 5%, конечно, будет медленнее, но это мало кого взволнует.

Бывает и ещё более хитрый JIT, в целиком динамических языках, типа smalltalk и python, который гененрит разные куски родного кода под разные наборы типов параметров -- типы-то динамические. Когда есть много статистики и памяти, можно сделать кучу неожиданных оптимальных вещей :)

[109.livejournal.com]

по-моему, извлечь адрес виртуальной функции из VMT (одна инструкция) - быстрее, чем вычислить "if x instanceof A", так что где выигрыш?

тут мне, впрочем, уже сказали, что компилятор в состоянии понять и заинлайнить в случае

A a = new A();
a.foo();

[nine_k]

1) Речь не о скорости извлечения, а о том, что процессор ничего про VMT не знает и предвыборку по адресу из неё не осуществит, а заинлайненный код, показанный выше, рискует весь оказаться в prefetch queue и соотв. все его инструкции имеют шанс быть заранее в какой-то мере исполненными, или хоть целиком дешифрованными, ко времени их очередного исполнения. Выборка-то нынче дорога.

2) Речь не о статических компиляторах (которые, конечно, много что могут), а о JIT, т.е. кодогенерации в runtime. У статического компилятора есть граф зависимостей, у JIT -- заодно и статистика настоящего исполнения кода, что может иногда вести к решениям, которые статический компилятор просто не в силах придумать, за неимением этой статистики.

[109.livejournal.com]

ах да, prefetch.

теперь я про jit не понимаю :-)

он же не каждое исполнение компилирует, а только первое, когда ещё нет никакой статистики?

[nine_k]

JIT компилирует не сразу, а именно just in time, т.е. набрав статистику. Что-то компилируется после N вызовов, что-то перекомпилируется и инлайнится после M > N вызовов, etc. Большая часть кода исполняется редко, а компилируется только самое частое за последнее время, по результатам непрерывного профилирования.

[109.livejournal.com]

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

[nine_k]

Компиляция стоит времени и памяти (на откомпилированное в том числе).
Компиляция после N > 2-го вызова имеет смысл потому, что набрана статистика на тему, как именно оптимизировать данный кусок, в реальных условиях приложения. Разумеется, если можно позволить себе компиляцию перед первым вызовом, это тоже хорошо. Но не всегда возможно: так придётся компилировать код, который исполнится 1-2 раза и больше не пригодится. Куда интереснее оптимально скомпилировать critical path.

С другой стороны, CLI-шный Ngen.exe умеет сначала статически (до загрузки и исполнения) скомпилировать байткод в родной, а потом дооптимизировать (перекомпилировать) критические куски по ходу выполнения.

Хороших ссылок что-то не найду; всё лезет или совсем популярно "что тако JIT вообще", или длинные специализированные учёные статьи.