наносекунды к миллисекундам - быстрое подразделение 1000000

Я удивлен, что никто этого еще не понял…

• деление - то же самое, что умножение на дробь
• умножение на дробную степень 2 выполняется быстро: просто сдвиг бит
• целочисленное деление включает округление в меньшую сторону
• округление в меньшую сторону похоже на умножение на несколько меньшую дробь (до определенного момента вам нужно знать свои диапазоны)

Итак,

const uint64_t numerator = (1LL<<32)/1000000;

...

millionths = ( number * numerator ) >> 32;

Супер быстро!

Умножить на 1 / 1,000,000. Это должно быть быстрее. Мой поиск в Google говорил, что для ускорения деления умножение должно быть обратным. Поэтому я бы предварительно вычислил обратную величину или список обратных, если есть относительно известный набор возможных значений, а затем умножил бы.

Джейкоб

Однако я делаю это довольно часто и задаюсь вопросом, может ли это стать узким местом.

Перво-наперво. Если вы думаете, что это будет узкое место, профилируйте код, о котором идет речь, и выясните наверняка.

Если (и только если) это ваше узкое место, работайте над его улучшением.

Теперь о вариантах улучшения:

1. Возможно, вам не потребуется сразу переводить в миллисекунды. Если вы просто собираете данные, просто сохраните полное 64-битное число, возвращаемое функцией gethrtime () , и покончите с этим. Все, что человеку нужно прочитать, может быть подвергнуто постобработке позже или с гораздо меньшей частотой обновления.

2. Если вы синхронизируете какое-то повторяющееся событие, вы можете попробовать выполнить деление на разнице между двумя вызовами, которая должна быть очень маленькой, если вы вызываете gethrtime () достаточно часто, чтобы возникло узкое место:

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

3. Вы можете реализовать fastDivByOneMillion () как умножение и деление на степень двойки:

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

Примечания:

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

Как Джошуа Хаберман упомянул , ваш компилятор, вероятно, уже преобразует деление на константу 1000000 в умножение на «магическое число» с последующим сдвигом (если деление является целочисленной операцией). Вы можете получить более подробную информацию о том, что происходит в книге Генри Уоррена "Hacker's Delight" и на сопутствующем веб-сайте:

• http://www.hackersdelight.org/

У него даже есть страница с калькулятором Javascript для магические числа:

• http://www.hackersdelight.org/magic.htm

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

Во-вторых, насколько точным должен быть результат? Удобное практическое правило для преобразования двоичного числа в десятичное: 2 ^ 10 ~ = 10 ^ 3.

Другими словами, миллион примерно равен 2 ^ 20. Так что вы можете просто сдвинуть вправо 20. Компилятор, конечно, не сделает этого за вас автоматически, потому что он изменит результат. Но если вы готовы жить с небольшой точностью, и разделение на самом деле реальная проблема производительности, это было бы моим предложением.

Целочисленное деление можно преобразовать в серию более простых операций. Общий метод, который популяризировал Терье Матисен, описан на стр. 136 Оптимизация подпрограмм на ассемблере . Если вы заранее знаете ширину ваших типов данных и то, на что вы делите, это научит вас, как превратить это в серьезные из более простых операций, которые теоретически могут быть быстрее, чем более общая операция деления, которая должна обрабатывать любой делитель. Если вы беспокоитесь о целых числах разного размера в некоторых из них, по-прежнему будут возникать некоторые проблемы с платформой.

процесс над реализацией разделения SPARC. Может быть, если вы используете явно древний процессор SPARC V7, еще до того, как разделение было реализовано на аппаратном уровне , вы могли бы получить некоторые улучшения, но даже тогда я Я сделал ставку на то, что встроенное разделение будет быстрее.

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

Если вы можете обойтись с этим, вот мое решение.

• используют целые числа вместо чисел с плавающей запятой (они быстрее)
• делят на 1048576, сдвигая биты вправо (то есть на дешевле , чем что-либо с числами с плавающей запятой)

и убедите себя, что миллисекунды должны быть base2, а не base10. ; -)

1/1000000 равно 0,000000000000000000 0100 0011 0001 1011 1101 1110 1000 0010 1101 0111 1011 0110 0011 01 двоичный - что составляет 0x431BDE82 * 2 ^ -18

Следовательно, n / 1000000 равно эквивалентно (n * 0x431BDE82) >> 18

Также n / 1000000 эквивалентно (n * 0x8637BD04) >> 19

Обратите внимание, что это расчет с «фиксированной точкой», и вы должны знать, что точность может быть проиграл.

Создайте сценарий bash с именем client.sh:

#!/bin/bash

cat someFile

while read FOO; do
        echo $FOO >&3
        if [[ $FOO =~ `printf ".*\x00\x1c.*"` ]]; then
                break
        fi
done

Затем вызовите netcat из основного скрипта, например, так:

3>&1 nc -c ./client.sh somehost 1234

(Вам понадобится версия bash 3 для сопоставления регулярных выражений).

Это предполагает, что сервер отправляет данные по строкам - в противном случае у вас будет настроить client.sh так, чтобы он читал и отображал символ за раз.

Все люди, рекомендующие математические приемы, либо имеют плохие компиляторы, либо недооценивают свои компиляторы. Например, попробуйте скомпилировать эту функцию:

unsigned long div1000000(unsigned long n) {
  return n / 1000000UL;
}

Скомпилировано с помощью gcc 4.3.3 на x86 (-O3, -fomit-frame-pointer), я получаю:

$ objdump -d div.o -M intel

test2.o:     file format elf32-i386


Disassembly of section .text:

00000000 <div1000000>:
   0:   b8 83 de 1b 43          mov    eax,0x431bde83
   5:   f7 64 24 04             mul    DWORD PTR [esp+0x4]
   9:   c1 ea 12                shr    edx,0x12
   c:   89 d0                   mov    eax,edx
   e:   c3                      ret    

Другими словами, компилятор взял n / 1000000UL и превратил его в (unsigned long long) (n * 0x431bde83) >> (0x12 + 32) . Почему это работает? Сверху в голове, понятия не имею! Но компилятор решил, что это будет быстрее, чем выполнение собственного деления.

Мораль истории:

• не оптимизируйте это, если вы не уверены, что это узкое место.
• не выполняйте причудливую арифметику ( умножение на обратное, сдвиги и т. д.), если вы еще не знаете, что делает ваш компилятор, и не думаете, что можете его превзойти.
• сравните результат - оставьте в бородавке вроде причудливой битовой математики, только если вы продемонстрировали, что превзошли свой компилятор.
• 1227]