memset - самая быстрая функция

[VVWVV]

Описание:

Заполняет все ячейки массива переданным значением.

Параметры:

array[] - массив/строковая переменная, в которую будет записан результат
val - заполняемое значение

Возвращаемое значение:

Всегда возвращает нуль.

Плюсы реализации:

Быстрое заполнение. В 4-5 раз быстрее варианта от Slice.

Минусы реализации:
Несовместимость с JIT-плагином.

Код:


stock memset(array[], val, size = sizeof array) {
#pragma unused array, val

static
amx_header[AMX_HDR],
bool:is_amx_header_initialized = false;


if (0 == _:is_amx_header_initialized) {
is_amx_header_initialized = true;
GetAmxHeader(amx_header);
}

new
base,
ctx[AsmContext],
cod = -(amx_header[AMX_HDR_DAT] - amx_header[AMX_HDR_COD]);

#emit CONST.pri memset
#emit LOAD.S.alt cod
#emit ADD
#emit STOR.S.pri base

AsmInitPtr(ctx, base, 200);

@emit PROC
@emit LOAD.S.alt 12
@emit LOAD.S.pri 16
@emit FILL (size << 2)
@emit RETN

#emit LCTRL 5
#emit SCTRL 4
#emit CONST.pri memset
#emit ADD.C 4
#emit SCTRL 6

return 0;
}


stock memset(array[], val, size = sizeof array)
{
#pragma unused array, val
static
fill_inst_offset;
if (fill_inst_offset == 0) {
#emit lctrl 6
#emit move.alt // 4
#emit lctrl 0 // 8
#emit add // 4
#emit move.alt // 4
#emit lctrl 1 // 8
#emit sub.alt // 4
#emit add.c 92 // 8
#emit stor.pri fill_inst_offset // 8
} {} //
#emit load.s.pri size // 8
#emit shl.c.pri 2 // 8
#emit sref.pri fill_inst_offset // 8
#emit load.s.alt 12 // 8
#emit load.s.pri 16 // 8
#emit fill 1 // 4
#emit zero.pri
#emit retn
}


Тесты:

Количество итераций: 1 000 000
1) Размер массива: 100

memset(VVWVV without AMX_asm): 423ms
memset(Владокс): 729ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 2270ms
2) Размер массива: 10 000

memset(VVWVV without AMX_asm): 7920ms
memset(Владокс): 8336ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 12001ms


Пример использования:


main()
{
new array[1000] = {1000,1000+1,...};

print(!"Before:");
printf("0: %d", array[0]);
printf("499: %d", array[499]);
printf("999: %d", array[999]);

memset(array,6);

print(!"After:");
printf("0: %d", array[0]);
printf("499: %d", array[499]);
printf("999: %d", array[999]);
}


См. также:

[Function] GetNumberOfArguments (http://pro-pawn.ru/showthread.php?14689)
[Function] Чистим массив игрока (http://pro-pawn.ru/showthread.php?7931)
[Function] Защита от DeAMX (new) (http://pro-pawn.ru/showthread.php?8277)
[Function] ClearKillFeed (http://pro-pawn.ru/showthread.php?12295)
[Function] dc_SleepFix (http://pro-pawn.ru/showthread.php?13188)
[Function] GetNumberOfPublics (http://pro-pawn.ru/showthread.php?14704)
[Function] GetStackSize (http://pro-pawn.ru/showthread.php?10824)
[Function] itos (http://pro-pawn.ru/showthread.php?3243)
[Function] formatnum (http://pro-pawn.ru/showthread.php?14766)


Автор: VVWVV

Копирование данной статьи на других ресурсах без разрешения автора запрещено.

[Daniel_Cortez]

Готов поспорить, есть способ и получше: использовать всего одну инструкцию fill, но перед её выполнением перезаписывать аргумент: количество ячеек для заполнения указанным значением. По сути это ни что иное, как модификация кода. Можно даже попробовать обойтись безо всяких amx_assembly.

[VVWVV]

Готов поспорить, есть способ и получше: использовать всего одну инструкцию fill, но перед её выполнением перезаписывать аргумент: количество ячеек для заполнения указанным значением. По сути это ни что иное, как модификация кода. Можно даже попробовать обойтись безо всяких amx_assembly.

Т.е. ты предлагаешь такой вариант?


stock memset(array[], val, size = sizeof array)
{
size <<= 2;
#emit LOAD.S.alt 12
#emit LOAD.S.pri 16
#emit FILL size
}

[Daniel_Cortez]

Т.е. ты предлагаешь такой вариант?


stock memset(array[], val, size = sizeof array)
{
size <<= 2;
#emit LOAD.S.alt 12
#emit LOAD.S.pri 16
#emit FILL size
}

Не совсем. Аргумент инструкции fill представляет собой целочисленную константу, т.е. перед выполнением fill нужно перезаписывать тот аргумент в секции кода.


memset(array[], value, size = sizeof(array))
{
goto rewrite_fill_arg;
do_fill:
#emit load.s.alt array
#emit load.s.pri value
#emit fill 1
#emit zero.pri
#emit retn
rewrite_fill_arg:
static fill_arg_offset = 0;
if (fill_arg_offset != 0)
{ // Горячий путь: смещение аргумента fill уже вычислено
#emit load.alt fill_arg_offset
#emit load.s.pri value
#emit stor.i
goto do_fill;
}
// (Здесь вычисление адреса аргумента)
#emit load.alt fill_arg_offset
#emit load.s.pri value
#emit stor.i
goto do_fill;
}

[VVWVV]

Не совсем. Аргумент инструкции fill представляет собой целочисленную константу, т.е. перед выполнением fill нужно перезаписывать тот аргумент в секции кода.


memset(array[], value, size = sizeof(array))
{
goto rewrite_fill_arg;
do_fill:
#emit load.s.alt array
#emit load.s.pri value
#emit fill 1
#emit zero.pri
#emit retn
rewrite_fill_arg:
static fill_arg_offset = 0;
if (fill_arg_offset != 0)
{ // Горячий путь: смещение аргумента fill уже вычислено
#emit load.alt fill_arg_offset
#emit load.s.pri value
#emit stor.i
goto do_fill;
}
// (Здесь вычисление адреса аргумента)
#emit load.alt fill_arg_offset
#emit load.s.pri value
#emit stor.i
goto do_fill;
}


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

[Daniel_Cortez]

Вполне рационально, если знать набор инструкций AMX.

<адрес аргумента fill> = <физ. адрес блока памяти с кодом> - <физ. адрес блока памяти с данными> + <адрес функции memset> + <смещение аргумента fill от начала функции>
Из этих составляющих смещение аргумента найти очень легко - это 32 бита: 4 на опкод proc, 8 - на jump, ещё по 8 на load.s.pri/alt и оставшиеся 4 сам опкод fill, без аргумента.
По поводу физических адресов секций кода и данных уже не помню, но они как-то находились в YSI.

[VVWVV]

Вполне рационально, если знать набор инструкций AMX.

<адрес аргумента fill> = <физ. адрес блока памяти с кодом> - <физ. адрес блока памяти с данными> + <адрес функции memset> + <смещение аргумента fill от начала функции>
Из этих составляющих смещение аргумента найти очень легко - это 32 бита: 4 на опкод proc, 8 - на jump, ещё по 8 на load.s.pri/alt и оставшиеся 4 сам опкод fill, без аргумента.
По поводу физических адресов секций кода и данных уже не помню, но они как-то находились в YSI.

Хорошо. Ты меня убедил.. Но всё же мне это не очень нравится.

Пожалуй, добавлю твой вариант. В скором времени добавлю тесты.

UPD: Как оказалось, такой алгоритм уже существует в открытом доступе. Его подготовил так называемый BJIADOKC. Если говорить о скорости, то его алгоритм выигрывает.



stock memset3(array[], value, size = sizeof(array))
{
if(!size)
{
print("memset: Не указан размер массива");

/*
//размер массива
#emit ADDR.pri array
#emit ADD.c 4
#emit PUSH.pri
#emit SHL.C.pri 2

//вызов заного
#emit LREF.S.alt value
#emit LCTRL 1
#emit POP.alt
#emit JZER
#emit CALL.pri
*/

return 0;
}

new phys_addr;

#emit LOAD.S.pri array
#emit STOR.S.pri phys_addr

/*return */memfill_byaddr(phys_addr, value, size);
}

stock memfill_byaddr(address, cellsize, value)
{
new idx;

#emit LCTRL 6 //FIXME: #emit SCTRL 3
#emit MOVE.alt
#emit LCTRL 0 //FIXME: #emit LCTRL 2

/*
#emit LBL.S ADDR
#emit PUSH.S
idx += heapspace() - ADDR:0x97A1B35C;
*/

#emit ADD
#emit MOVE.alt

//#emit POP.pri

#emit LCTRL 1
#emit SUB.alt
#emit ADD.C 92

//#emit LOADB.I

#emit STOR.S.pri idx
#emit LOAD.S.pri cellsize
#emit SHL.C.pri 2
#emit SREF.S.pri idx

#emit LOAD.S.alt address
#emit LOAD.S.pri value
#emit FILL 0
}



UPD(2): Проверяя данный алгоритм, выяснил, что его алгоритм не полностью заполняет массив, а только частично.
UPD(3): Алгоритм всё же работает, но, как выяснилось, он немного медленнее алгоритма ниже. Проблема была в том, что автор функции неправильно указал параметры memfill_byaddr при вызове.

Сделал так, как ты и предлагал:


memset(array[], value, size = sizeof(array))
{
static
fill_inst_offset;
if (fill_inst_offset == 0) {
#emit lctrl 6
#emit move.alt // 4
#emit lctrl 0 // 8
#emit add // 4
#emit move.alt // 4
#emit lctrl 1 // 8
#emit sub.alt // 4
#emit add.c 92 // 8
#emit stor.pri fill_inst_offset // 8
} {} //
#emit load.s.pri size // 8
#emit shl.c.pri 2 // 8
#emit sref.pri fill_inst_offset // 8
#emit load.s.alt 12 // 8
#emit load.s.pri 16 // 8
#emit fill 1 // 4
#emit zero.pri
#emit retn
}

[Daniel_Cortez]

Сделал так, как ты и предлагал:


memset(array[], value, size = sizeof(array))
{
static
fill_inst_offset;
if (fill_inst_offset == 0) {
#emit lctrl 6
#emit move.alt // 4
#emit lctrl 0 // 8
#emit add // 4
#emit move.alt // 4
#emit lctrl 1 // 8
#emit sub.alt // 4
#emit add.c 92 // 8
#emit stor.pri fill_inst_offset // 8
} {} //
#emit load.s.pri size // 8
#emit shl.c.pri 2 // 8
#emit sref.pri fill_inst_offset // 8
#emit load.s.alt 12 // 8
#emit load.s.pri 16 // 8
#emit fill 1 // 4
#emit zero.pri
#emit retn
}

Что на счёт скорости работы этой функции, в частности, в сравнении с вариантом в 1-м посте?
И да, ты проверял, как эта функция компилируется при разных значениях флагов -d и -O? Например, при -d(1/2/3) компилятор дополнительно ставит инструкции break для отладчика (которого в SA-MP, конечно же, нет), а при -O1 оптимизирует генерируемый байткод, что может повлиять на используемую комбинацию опкодов в выражении if - если эта комбинация будет занимать меньше или больше места, то смещение инструкции fill тоже станет другим.

[VVWVV]

Что на счёт скорости работы этой функции, в частности, в сравнении с вариантом в 1-м посте?
И да, ты проверял, как эта функция компилируется при разных значениях флагов -d и -O? Например, при -d(1/2/3) компилятор дополнительно ставит инструкции break для отладчика (которого в SA-MP, конечно же, нет), а при -O1 оптимизирует генерируемый байткод, что может повлиять на используемую комбинацию опкодов в выражении if - если эта комбинация будет занимать меньше или больше места, то смещение инструкции fill тоже станет другим.

Скорость работы в разы быстрее, чем в первом посте.

Это было очевидно. Но повлиять это вряд ли сможет, ведь отсчёт идёт от инструкции lctrl 6. И при включении/выключении флагов меняется только то, что выше этой инструкции.

-O0 -d3


proc ; memset
; line e9
break ; 118
;$lcl size 14
;$lcl value 10
;$lcl array c
; line ea
break ; 11c
; line ec
break ; 120
load.pri cc
zero.alt
eq
jzer 18
;$exp
lctrl 6
move.alt ; Начало
lctrl 0
add
move.alt
lctrl 1
sub.alt
add.c 5c
stor.pri cc
l.18 ; 174
load.s.pri 14
shl.c.pri 2
sref.pri cc
load.s.alt c
load.s.pri 10
fill 0
zero.pri
retn
zero.pri
retn


-O1 -d0


proc ; memset
; line e9
;$lcl size 14
;$lcl value 10
;$lcl array c
; line ea
break ; e8
; line ec
break ; ec
load.pri cc
jnz 18
;$exp
lctrl 6
move.alt ; Начало
lctrl 0
add
move.alt
lctrl 1
sub.alt
add.c 5c
stor.pri cc
l.18 ; 138
load.s.pri 14
shl.c.pri 2
sref.pri cc
load.s.alt c
load.s.pri 10
fill 0
zero.pri
retn
zero.pri
retn


Тесты:
Количество итераций: 1 000 000

Без JIT:
1) Размер массива: 100
memset(VVWVV without AMX_asm): 423ms
memset(Владокс): 729ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 2270ms
2) Размер массива: 10 000
memset(VVWVV without AMX_asm): 7920ms
memset(Владокс): 8336ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 12001ms

C JIT:
1) Размер массива: 100
memset(VVWVV without AMX_asm): 17ms
memset(Владокс): 30ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 117ms
2) Размер массива: 10 000
memset(VVWVV without AMX_asm): 17ms
memset(Владокс): 31ms (с фиксом аргументов, иначе она работала бы неправильно)
memset(Slice): 2130ms

[vovandolg]

зачем компилировать с JIT если JIT плагин не поддерживает корректно emit конструкции

[Daniel_Cortez]

зачем компилировать с JIT если JIT плагин не поддерживает корректно emit конструкции
Директивами #emit занимается компилятор. Для JIT инструкции, сгенерированные из "традиционного" кода на Pawn и из #emit абсолютно одинаковы.

Кстати про JIT...

VVWVV, забыл сказать, что с предложенным мной подходом нельзя будет использовать JIT, т.к. с ним невозможна модификация кода во время выполнения. Максимум можно модифицировать код при вызове коллбэка OnJITCompile, непосредственно перед JIT-компиляцией.

[VVWVV]

VVWVV, забыл сказать, что с предложенным мной подходом нельзя будет использовать JIT, т.к. с ним невозможна модификация кода во время выполнения. Максимум можно модифицировать код при вызове коллбэка OnJITCompile, непосредственно перед JIT-компиляцией.

Да, JIT преподносит большое количество ограничений для emit. В таком случае я изменю первый пост, добавив в него твой подход, а также ссылку на подход Slice.

Тем не менее, теперь появилось желание сделать все mem-функции в виде плагина (хотя возможно, что кто-то уже сделал это)

[VVWVV]

Обновлена функция под новый оператор __emit


stock memset(array[], value, size=sizeof array)
{ //pro-pawn.ru/showthread.php?14919
static fill_instruction_offset=0;
emit {
load.pri fill_instruction_offset
jnz fill_array
lctrl 6
move.alt
lctrl 0
add
move.alt
lctrl 1
sub.alt
add.c (cellbits / charbits * 23)
stor.pri fill_instruction_offset
fill_array:
load.s.pri size
shl.c.pri 2
sref.pri fill_instruction_offset
load.s.pri value
load.s.alt array
fill 1
}
return 0;
}

[Salik_Davince]

Отпала ли несовместимость с JIT плагином в последней версии?

[Daniel_Cortez]

Код с расчётом адреса инструкции fill можно было сделать немного эффективнее. В последних версиях компилятора (3.10.7 и 3.10.8) можно указать метку в качестве аргумента const.pri и add.c:

lctrl 1
move.alt
lctrl 0
sub
add.c :fill_instr
add.c (cellbits / charbits)

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

Для тех же случаев, когда аргументы value и size являются константами (а таких случаев подавляющее большинство), можно поступить намного проще:

// memset(array, value)
#define memset(%0,%1) \
emit(const.pri (%1), const.alt %0, fill (sizeof(%0) * (cellbits / charbits)))

[Salik_Davince]

Можете объяснить почему нету совместимости с JIT, в нем не работают какие-то инструкции? И какой вариант совместим с JIT ?

[Daniel_Cortez]

Можете объяснить почему нету совместимости с JIT, в нем не работают какие-то инструкции?
Потому что функция модифицирует свой код (на самом деле всего 1 инструкцию) при каждом вызове - с JIT модификация кода не имеет эффекта.


И какой вариант совместим с JIT ?
Предложенный мной выше вариант должен работать с JIT, но он подойдёт не во всех случаях (опять же, выше расписано, почему и как).