Pull to refresh
16
Karma
0
Rating
Evgeny Astigeevich @eastig

User

  • Followers 1
  • Following

Прогресс GC от JDK 8 до JDK 17

Быстрое сравнение double

Странно, у меня на ARM64 этот код дает неправильный результат. Вот такой код работает:


  begin = clock();
  min = 1e200;
  int64_t min64 = to_int64(min);
  next = 1;
  long j = -1;

  for (long i=0; i<size; i++) {
    // next = 1./(next+1);
    int64_t x = to_int64(gig[i]);
    if (x < min64) {
      min64 = x;
      j = i;
    }
  }
  end = clock();

Результат:


3GB random doubles generated
next: 1.000000e+00 min: -1.797693e+308 time: 0.725408
next: 1.000000e+00 min: -1.797693e+308 time: 0.511060

Можно переименовать статью: ускорения поиска минимального числа в массиве вещественных чисел.
Но как только в цикле появится переход от целого к вещественному, то все ускорение пропадет.

Быстрое сравнение double

А можно ассемблерный код?

Быстрое сравнение double

Потому что GCC предполагает, что для работы с double будут использоваться в основном FP инструкции, что в целом правда. Так как целочисленных регистров всегда не хватает, компилятор старается использовать все другие регистры.
Кстати в коде для x86_64, значения также пересылаются из FP регистров XMM в целочисленные регистры. И это код сгенерированный clang.

Быстрое сравнение double

AArch64, Neoverse N1


$ gcc --version
gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12)
$ gcc -O3 test.c
$ ./a.out
3GB random doubles generated
next: 6.180340e-01 min: -1.797693e+308 time: 2.417564
next: 6.180340e-01 min: -1.797693e+308 time: 2.417601
$ gcc -O3 test_nodiv.c
$ ./a.out
3GB random doubles generated
next: 1.000000e+00 min: -1.797693e+308 time: 0.725358
next: 1.000000e+00 min: -1.797693e+308 time: 1.451623

Получается, что нативная реализация в 2 раза быстрее.
Ассемблерный код:


.L6: // цикл с нативным сравнением
    ldr d0, [x21, x0, lsl 3]
    add x0, x0, 1
    fcmp    d0, d8
    fcsel   d8, d8, d0, pl
    cmp x0, x1
    bne .L6
...
.L8: // цикл с is_smaller
    ldr d0, [x21, x0, lsl 3]
    fmov    x1, d8
    add x0, x0, 1
    fmov    x3, d0
    asr x2, x1, 63
    eor x2, x1, x2, lsr 1
    asr x1, x3, 63
    eor x1, x3, x1, lsr 1
    cmp x2, x1
    fcsel   d8, d8, d0, le
    cmp x0, x4
    bne .L8

Видно, что в цикле с is_smaller нам приходится пересылать значения из FP регистров D0/D8 в целочисленные регистры X1/X3. Цикл с is_smaller содержит в 2 раза больше инструкций.

Быстрое сравнение double

Сомнительное преимущество:


  1. FPU большую часть времени простаивают, так как количество целочисленных инструкций заведомо больше. Если только это не в ручную написанный код.
  2. Пересылка данных между целочисленными регистрами и FP регистрами не бесплатно, на ARM'ах 2-3 такта.

Есть у вас результаты бенчмарок, показывающие преимущество вашего подхода?

Быстрое сравнение double

В ARM AArch64 есть инструкции специально для этого: FCMP и FCM*, которые исполняются за 2-3 такта: https://godbolt.org/z/cr4Mcq
На x86_64 — UCOMISD.

Профилирование в продакшене для поиска узких мест на сервере

Как занимающийся анализом производительности cloud Java приложений, очень рекомендую вышедшее недавно второе издание книги:
Systems Performance, Enterprise and the Cloud, Second Edition by Brendan Gregg


Автор широко известен в области performance analysis, senior performance architect at Netflix.

Как пройти собеседование в FAANG: статистика

На самом деле, большинство задач, включая design interview, которые дают на собеседованиях в FAANG не такие уж и сложные. Думаю где-то 99% тех что мне давали. Да был 1% задач, которые были реально сложные. Вся проблема заключается в стрессе. Как только человек научится контролировать стресс, он успешно будет проходить любые интервью при условии наличия нормальных технических способностей. К сожалению нет silver bullet как держать под контролем этот стресс. Каждый должен найти свой метод.


На мой взгляд, составляющие успеха:


  • умение преодолевать стресс: 30%
  • хорошее знание английского языка и умение ясно коммуницировать: 30%
  • технические навыки решения задач: 25%
  • хорошее резюме: 10%
  • везение: 5%

Как пройти собеседование в FAANG: статистика

Хочу поделиться своим опытом прохождения собеседований в Google (2 неудачных onsite), Facebook (1 неудачное onsite, несколько заваленных скрининг), Apple (несколько заваленных скрининг) и Amazon (2 onsite, одно заваленное скрининг).


Выпусникам вузов и Juniors, и в какой-то степени Middles, проще пройти собеседования чем Seniors, так как у них проверяют только основные навыки: основы CS, способность решать задачи и коммуницировать решение. Им больше прощают ошибки. У них только одна проблема — это, чтобы их заметили и пригласили на собеседование. Просто так отправка резюме в компании вряд ли поможет. Здесь сильно помогает посещение конференций, знакомые, особенно linkedin, стажировка в крупных компаниях. Им как раз сильно должны помочь всякие LeetCode и книжки про прохождение собеседований. Чаще всего их собеседуют без особой связи с позицией на которую подался человек.


От Seniors ожиданий больше, особенно Design Interview. Оно будет практически одним из самым главных критериев оценки. Seniors будут стараться задать как можно больше вопросов разной сложности. Поэтому очень важно уметь быстро писать код при недостатке времени. Как только код написан и доказана его корректность, начинается процесс обсуждения того как его можно улучшить. Чаще всего это и есть главный этап собеседования. Если все время ушло на написание и отладку и не хватило на обсуждение, то результат скорее всего будет негативный. Для Seniors больше шансов пройти интервью, если опыт в резюме пересекается с позицией, на которую собеседуют. Все мои попытки пройти собеседования на Generally Smart Software Engineer, провалились практически после пары первых раундов. Собеседования на позиции, где мой опыт был бы полезен, практически все заканчивались onsite интервью. Процесс подготовки Seniors отличается от процесса подготовки Juniors/Middles и занимает минимум три месяца. Оптимально — шесть. От книжек пользы не много, особенно от всюду рекламируемой Cracking the Coding Interview. За время ее существования вышла куча статей в Интернете с ее пересказом. Так что проще прочитать пару-тройку этих статей. Все другие книги пишутся как под копирку. Для подготовку к Coding Interview, я рекомендую книги по спортивному программированию. Мне больше всего помогла Guide to Competitive Programming: Learning and Improving Algorithms Through Contests. LeetCode полезен только в начале, для выработки и поддержания навыка решения задач. Больше месяца-двух тратить на него смысла нет. Можно стать умельцем решения задач LeetCode. Процесс решения задач на интервью все таки отличается. И да, не нужно ставить цель прорешать и запомнить все задачи. От этого пользы мало, так как задач очень много и их решения невозможно запомнить. Интервальные методы запоминая тут не помогут.


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


Полезно проходить собеседования в разные компании, для тренировки. Вот тут независимые рекрутеры могут быть полезны, так как они подготовят список таких компаний и быстро сведут с ними. Только не проговоритесь, что это вам для тренировки. Эти собеседования вам помогут улучшить коммуникационные навыки и стрессоустойчивость. Особо не надейтесь что они помогут вам подготовиться к техническим интервью FAANG.


Телефонные интервью — это по большей части лотерея. Способность быстро решать задачки на время увеличивает шансы выиграть в нее.


Onsite интервью — это тоже лотерея, но уже с большей вероятностью выйгрыша.


Будьте готовы к встрече с людьми с завышенным чувством собственного значения. Таким людям не нравится, когда ответ не совпадает с тем, что они хотят услышать. К счастью таких людей попадается очень мало. По большей части собеседования, особенно onsite, в FAANG оставляют приятные впечатления.


Очень помогает понимание того, что процесс собеседования в FAANG, нацелен прежде всего на минимизацию найма некомпетентного сотрудника. То что вы не прошли, еще не значит, что у вас больше нет шансов попасть в FAANG. Я в итоге прошел собеседования в Amazon и принял офер.


Если есть вопросы, спрашивайте, буду рад ответить.

Сравнение компиляторов ARMCC, IAR и GCC

В бытность, когда был вовлечен в разработку ARMCC 6, у LTO была проблема удаления символов, которые линкер посчитал ненужными, но они на самом деле нужны. Если это этот случай, то нужно поиграть с опциями линкера developer.arm.com/documentation/101754/0615/armlink-Reference/armlink-Command-line-Options/--lto-keep-all-symbols----no-lto-keep-all-symbols
Еще можно поиграть с developer.arm.com/documentation/101754/0615/armlink-Reference/armlink-Command-line-Options/--lto-level

Android изнутри: сравнение Dalvik и ART

Это затруднительно сделать в силу большого разнообразия версий Android и производителей телефонов.

Android изнутри: сравнение Dalvik и ART

 Например исправили security bug в Java core или framework библиотеках. Насколько я помню любое изменение в системных компонентах требовало перекомпиляции всех приложений, но могу и ошибаться.

Android изнутри: сравнение Dalvik и ART

Кстати, в ART JIT-компилятор и AOT-компилятор — это один и тот же компилятор, который запускают либо в режиме JIT или AOT. AOT-компилятор можно запустить через утилиту dex2oat.

Android изнутри: сравнение Dalvik и ART

В статье не говорится, почему вернулись к схеме Interpreter+JIT+AOT. Основная проблема с AOT была, что при любом изменении системы приходилось перекомпилировать все библиотеки и приложения, что могло занимать много времени. При переходе на Interpreter+JIT+AOT одним из критериев был не ухудшение времени запуска. После перехода выяснилось, что не весь код приложений нужно компилировать.

В ART применяется многократная AOT перекомпиляция кода в зависимости от изменения профиля исполнения. Кроме того Google Play может предоставлять некий профиль исполнения приложения, который учитывается при установке приложения.

В Android 10 и 11 случился APEX. Теперь ART может обновлять через Google Play, если производитель телефона поддерживает эту функцию.

Сколько инструкций процессора использует компилятор?

В теории может, но на практике я этого в LLVM не видел.

что LIR load при кодогенерации на АРМе может распадаться на ldr,ldp,ld1,ld2,ld3,ld4 вас не убеждает


Такие вещи могут делать в LLVM backend'е, где оперируют MIR (https://llvm.org/docs/MIRLangRef.html).
Вначале MIR стараются получить как можно близко похожим на LIR. И он неоптимален. Затем этот MIR прогоняют через кучу оптимизаций, где могут делать свёртки/разбивки инструкций (strength reduction/peephole optimizations). Затем MIR трансформируют в MachineCode, который также прогоняют через оптимизации. И эти оптимизации пишутся под конкретный target ISA, где уже оперируют в терминах инструкций ISA.
Цепочка преобразований: LIR-MIR(здесь очень похожи на LIR)->MachineCode(здесь уже все дальше от IR)->Assembly
LLVM позволяет быстро создать кодогенератор с помощью TD файлов, где описывается mappping MIR в Target ISA. Так как этот кодогенератор сгенерированный, то он просто мепит одни инструкции на другие без особого анализа и обработки. Поэтому можно утверждать что исходный IR отображается практически один в один в target ISA.
Если в вашу ISA так просто IR не отобразить, то тогда нужно будет писать такое отображение ручками, где каждая инструкция MIR как-то сложно преобразуется.
LLVM разрабатывался таким образом, чтобы IR максимально легко было отображать на target ISA.
Я помню как мы добавляли ARMv8.x расширения к LLVM. На первом этапе — это просто создание td файлов описаний. Затем мы реализовывали специфичные оптимизации, и то если в этом есть необходимость.

Сколько инструкций процессора использует компилятор?

STM убрали, но добавили LDP/STP: load/store pair.

Сколько инструкций процессора использует компилятор?

А что в вашем понимании 1-to-1? Вы говорите:
но никаким one to one mapping тут и не пахнет.

Привидите пример того, сколько инструкций LIR отображается не один в один.
Все что с! — это метаданные, хинты для оптимизаций и кодогенерации. Они могут быть проигнорированы, либо вообще отброшены. Оптимизация не должна использовать метаданные для передачи информации влияющие на корректность операции.
Если отбросить метаданные то определение:
result = load [volatile], * [, align ]
И семантика простая:
«The location of memory pointed to is loaded. If the value being loaded is of scalar type then the number of bytes read does not exceed the minimum number of bytes needed to hold all bits of the type. For example, loading an i24 reads at most three bytes. When loading a value of a type like i20 with a size that is not an integral number of bytes, the result is undefined if the value was not originally written using a store of the same type.»

Сколько инструкций процессора использует компилятор?

Простые с точки зрения разработчика компилятора. А именно, каждая инструкция LIR делает только одно определенное действие, не имеет неявных зависимостей и обладает минимумом побочных эффектов. Инструкция явно предоставляет всю информацию о себе, что позволяет писать оптимизации на основе matching, пример InstrCombine pass. Наличие типов как раз упрощает их.
Если бы в IR были бы такие сложные x86 инструкции как 'LOOP' или 'REP CMPS', то всем оптимизациям приходилось бы каждый раз иметь в виду что инструкция делает больше чем одно действие. Это все затрудняет написание generic оптимизаций. Кстати интринсики в IR — это как раз и есть возможность использовать сложные инструкции. Только вот оптимизации не любят интринсики.
По поводу различных мнемоник, как раз простота IR позволяет автоматизировать процесс мэпинга инструкций IR в машинные инструкции. В LLVM за это отвечает tablegen, который берет описание ISA и генерирует таблицу конечного автомата.

Сколько инструкций процессора использует компилятор?

В исходниках LLVM eсть немного "#if defined(__i386__) || defined(__x86_64__)".
Но основное различие в том, поддержку каких targets включили при построении Clang/LLVM. Если все бинарники с llvm.org построены с одними и теми же настройками, то отличия должны быть минимальны.

Information

Rating
5,351-st
Location
Cambridge, England - East, Великобритания
Registered
Activity