Почему Trunc так медлителен?, Проверил в turbo pascal и Delphi7. Опции

[TarasBer]

Итак у нас, например, такая задача. Вещественное число из диапазона от 0 до 65535 преобразовать в word взятием целой части.

Это программа для дельфы.

program TruncTest;

{$APPTYPE CONSOLE}

uses
  SysUtils, Windows;

var
  i: longint;
  d, d1: double;
  d_w: array [0 .. 3] of word absolute d;
  k: word;
  T: longint;

begin
  d := 1234.5678;

  T := GetTickCount;
  for i := 0 to $FFFFFF do
    k := trunc(d);
  T := GetTickCount - T;
  WriteLn('Standart trunc: ', T);

  T := GetTickCount;
  for i := 0 to $FFFFFF do
    k :=  (word(d_w[3] shl 11) or (d_w[2] shr 5) or $8000)
      shr (14 - (d_w[3] shr 4 and $03FF));
  T := GetTickCount - T;
  WriteLn('My trunc: ', T);

  T := GetTickCount;
  for i := 0 to $FFFFFF do
    d1 := 1/d;
  T := GetTickCount - T;
  WriteLn('Floating point division: ', T);

  ReadLn;
end.

Программа на моём селероне с 600 мегагерцами вывела вот что:

Код

Standart trunc: 1913
My trunc: 681
Floating point division: 1582

Результат налицо - стандартный транк медленнее даже столь дорогостоящей операции, как вещественное деление. Изврат, использующий внутренню структуру типа double, оказался намного быстрее.

Для турбо паскаля аналогичная проверка выглядит так:

var
  i: longint;
  d, d1: double;
  k: integer;
  Time: longint absolute $0040: $006C;
  T: longint;
  d_w: array [0 .. 3] of word absolute d;

begin
  d := 1234.5678;

  T := Time; while T = Time do; T := Time;
  for i := 0 to $FFFFFF do
    k := trunc(d);
  T := Time - T;
  WriteLn('Standart trunc: ', T);

  T := Time; while T = Time do; T := Time;
  for i := 0 to $FFFFFF do
    k := ((d_w[3] shl 11) or (d_w[2] shr 5) or $8000)
      shr (14 - (d_w[3] shr 4 and $03FF));
  T := Time - T;
  WriteLn('My trunc: ', T);

  T := Time; while T = Time do; T := Time;
  for i := 0 to $FFFFFF do
    d1 := 1/d;
  T := Time - T;
  WriteLn('Floating point division: ', T);
end.

Программа показала вот что:

Код

Standart trunc: 58
My trunc: 7
Floating point division: 27

Тут результат ещё более на лицо.

Доктор, доктор, что мне делать по этому поводу?

[Account]

Лечиться собственным кодом

Сообщение отредактировано: Account - 3.01.2009 23:21

[volvo]

Доктор, доктор, что мне делать по этому поводу?

Использовать "изврат, использующий внутреннюю структуру double", если он у тебя работает быстрее... Только вот будет ли оно действительно настолько быстрее, если числа будут меняться - это вопрос... Маленький эксперимент:

  randomize;
  T := GetTickCount;
  for i := 0 to $FFFFFF do
    k := trunc(1 + random * 1000);
  T := GetTickCount - T;
  WriteLn('Standart trunc: ', T);

  T := GetTickCount;
  for i := 0 to $FFFFFF do
    k := FastTrunc(1 + random * 1000);
  T := GetTickCount - T;
  WriteLn('FastTrunc: ', T);

  T := GetTickCount;
  for i := 0 to $FFFFFF do begin
    d := 1 + random * 1000;
    k :=  (word(d_w[3] shl 11) or (d_w[2] shr 5) or $8000)
      shr (14 - (d_w[3] shr 4 and $03FF));
  end;
  T := GetTickCount - T;
  WriteLn('My trunc: ', T);

  T := GetTickCount;
  for i := 0 to $FFFFFF do
    d1 := 1 / (1 + random * 1000);
  T := GetTickCount - T;
  WriteLn('Floating point division: ', T);

- выдает уже

Standart trunc: 453
FastTrunc: 391
My trunc: 390
Floating point division: 610

, хотя исходный код выдавал

Standart trunc: 312
FastTrunc: 62
My trunc: 16
Floating point division: 16

, то есть, подавляющего преимущества уже нет...


Если есть SSE, то Trunc можно немного ускорить:

function myTrunc(X: single): integer;
asm
  CVTTSS2SI  eax, [ebp+offset X]
end;

, но на Селероне - вряд ли это применимо.

[TarasBer]

Дело в том, что я продолжаю гоняться за наивной детской мечтой реализовать полноценное 3д на Турбо Паскале. И в нём разница куда более заметна, чем в Дельфе.
И поэтому я не знаю, что такое FastTrunc, откуда он взялся, и зачем нужен тогда Trunc, если есть FastTrunc, а также, что за команда CVTTSS2SI.
Ещё вопрос - а стандартный trunc - это случайно не функция (всмысле что не макрос)? Может в этом всё дело?

И всё равно - непонятно, почему такая, казалось бы, простая команда не работает на порядок быстрее такой сложной команды, как деление?

Сообщение отредактировано: TarasBer - 4.01.2009 0:10

[volvo]

и зачем нужен тогда Trunc, если есть FastTrunc

FastTrunc - это уже дополнительно написанная функция, в "стандартном наборе" ее нет.

что за команда CVTTSS2SI

CVTTSS2SI—Convert with Truncation Scalar Single-Precision Floating-Point Value to Doubleword Integer

Description
Converts a single-precision floating-point value in the source operand (second operand) to a signed doubleword integer (or signed quadword integer if operand size is 64 bits) in the destination operand (first operand). The source operand can be an XMM register or a 32-bit memory location. The destination operand is a generalpurpose register. When the source operand is an XMM register, the single-precision floating-point value is contained in the low doubleword of the register. When a conversion is inexact, a truncated (round toward zero) result is returned. If a converted result is larger than the maximum signed doubleword integer, the floatingpoint invalid exception is raised. If this exception is masked, the indefinite integer value (80000000H) is returned.
In 64-bit mode, the instruction can access additional registers (XMM8-XMM15, R8-R15) when used with a REX.R prefix. Use of the REX.W prefix promotes the instruction to 64-bit operation. See the summary chart at the beginning of this
section for encoding data and limits.

а стандартный trunc - это случайно не функция (всмысле что не макрос)?

Нет, не макрос, именно функция... И на ее вызов тоже тратится время, ты прав...

Посмотрю, что можно сделать для TP...

[TarasBer]

Нет, не макрос, именно функция...

Это всё объясняет - вызов функции очень дорог. Непонятно только, как такая ошибка прокралась в дистрибутив Турбо Паскаля. Интересно, насколько этот факт полезен начинающим (и не только) програмистам?

Кстати, ваш пример с рандомом - плохой. Потому что больше всего времени занимал вызов этого самого рандома... Да ещё и умножение на 1000.

Сообщение отредактировано: TarasBer - 4.01.2009 0:25

[volvo]

Кстати, ваш пример с рандомом - плохой. Потому что больше всего времени занимал вызов этого самого рандома... Да ещё и умножение на 1000.

Ну, заменим генерацию и умножение на доступ к элементу массива, заполненного так:

var
  arr: array[0 .. $FFFFFF] of double;
...
  randomize;
  for I := 0 to $FFFFFF do begin
    arr[i] := random * 1000;
  end;

, получим:

Standart trunc: 328
FastTrunc: 78
My trunc: 110

, все равно преимущество "my trunc" над стандартной функцией только лишь трехкратное, но никак не 312/16=19-ти кратное, как это следует из твоего кода... Зато проверяется действительно время операции, а не (возможно) время выборки из памяти готового результата.

[volvo]

Кстати, вот вариант от Merlyn-а, который перекрывает по скорости и "Standard Trunc" и "My Trunc" из первоначального кода:

const Half: double = 0.5 ;
function chomp(Flt : double) : integer;
var result: integer;
begin
  asm
    fld Flt
    fsub Half
    fistp result
  end;
  chomp := result;
end;

, вот чего мне показал TP70:

Standart trunc: 38
chomp: 18
My trunc: 20
Floating point division: 8

[TarasBer]

const Half: double = 0.5 ;

asm
    fld d
    fsub Half
    fistp k
end

Я так понял, что это просто последовательность команд для сопроцессора, округляющая число? И минус 0.5 тут именно чтоб целая часть получилась. Проверил это у себя (естественно не в виде функции), получилось чуть быстрее моего варианта. Чтож, значит этой асмовставочкой и буду пользоваться.