быстрый sprintf
От: maks1180  
Дата: 01.11.22 00:13
Оценка:
Нужно реализовать быстрый sprintf, соотвественно:
1) передача размера буффера отпадает, так как придеться постоянно проверять не вышли ли мы за границы буфера, что существенно снизит скорость.
2) выделить буффер максимального размера (что-бы точно влезло), тоже не всегда получится.

Придумал следующие варианты sprintf:
Первый вариант:
1) парсит шаблон, переводит числа в строки (в память выделенную в стеке), считает длину строк, запоминает какие куски шаблона нужно исключить
2) тут мы знаем сколько нужно памяти, выделяем её либо в стеке либо получаем через callback функцию
3) собираем конечную строку используя заготовки из п1

Второй вариант:
1) выделяем память в стеке по мере парсинга шаблона.
Насколько я понимаю несколько вызовов alloca дадут единый кусок памяти общим объёмом не меньше чем сумма вызовов alloca. Это так ?

Проблему возврата памяти выделенной в стеке я описал в другом топике.

Как вам такие варианты ? Может я велосипед изобретаю и уже есть реализации данной задачи ?
===============================================
(реклама, удалена модератором)
Отредактировано 01.11.2022 0:15 maks1180 . Предыдущая версия . Еще …
Отредактировано 01.11.2022 0:14 maks1180 . Предыдущая версия .
Re: быстрый sprintf
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 01.11.22 00:53
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Насколько я понимаю несколько вызовов alloca дадут единый кусок памяти общим объёмом не меньше чем сумма вызовов alloca. Это так ?


Вот не факт

Вопрос такой — а что ты потом делаешь с этой строкой? Когда мне надо было сделать подобное на контроллере, я просто колбэк отдавал, который сразу в UART данные отправлял. Локально хранил только небольшой буфер для форматирования текущего числа
Маньяк Робокряк колесит по городу
Re[2]: быстрый sprintf
От: maks1180  
Дата: 01.11.22 01:45
Оценка:
M>>Насколько я понимаю несколько вызовов alloca дадут единый кусок памяти общим объёмом не меньше чем сумма вызовов alloca. Это так ?

M>Вот не факт


Как может быть по другому ? Что между вызовами alloca может занять стек ? Место для локальных переменных компилятор сразу выделяет в начале функции.


M>Вопрос такой — а что ты потом делаешь с этой строкой? Когда мне надо было сделать подобное на контроллере, я просто колбэк отдавал, который сразу в UART данные отправлял. Локально хранил только небольшой буфер для форматирования текущего числа


Функция которая вызвала будет обрабатывать эту строку, например может записать в файл или перекинуть в динамическую память.
===============================================
(реклама, удалена модератором)
Re[3]: быстрый sprintf
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 01.11.22 02:06
Оценка:
Здравствуйте, maks1180, Вы писали:

M>>Вот не факт


M>Как может быть по другому ? Что между вызовами alloca может занять стек ? Место для локальных переменных компилятор сразу выделяет в начале функции.


Место для локальных переменных выделяется в начале блока, в котором они определены. Если ты, например, в for'е будешь заводить переменные, то никакого непрерывного блока alloca не сможет сделать


M>>Вопрос такой — а что ты потом делаешь с этой строкой? Когда мне надо было сделать подобное на контроллере, я просто колбэк отдавал, который сразу в UART данные отправлял. Локально хранил только небольшой буфер для форматирования текущего числа


M>Функция которая вызвала будет обрабатывать эту строку, например может записать в файл или перекинуть в динамическую память.


Ну вот и передавай колбэки, которые пишут в файл или сохраняют в динамической памяти
Маньяк Робокряк колесит по городу
Re: быстрый sprintf
От: qqqqq  
Дата: 01.11.22 02:10
Оценка:
Вообще sprintf нетривиальная функция сама по себе даже без учета быстроты. Куча форматов, неизвестное количество аргументов. Можно долго кодить а потом еще дольше ошибки искать.
Отсюда можно начинать: https://codebrowser.dev/glibc/glibc/stdio-common/sprintf.c.html
Re: быстрый sprintf
От: Zhendos  
Дата: 01.11.22 12:03
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Нужно реализовать быстрый sprintf, соотвественно:


std::format и std::format_to есть.
Они много работы делают во время компиляции,
плюс std::format_to может в теории работать без
выделения памяти, если итератор будет в файл/устройство
результат записывать.
Re: быстрый sprintf
От: DiPaolo Россия  
Дата: 01.11.22 12:15
Оценка:
Для такой кастомизации нужно знать ваш контекст: как часто вызывается, какие данные, насколько они меняются от раза к разу, есть ли многопоточность, как часто надо писать (флашить) и прочее.

M>Нужно реализовать быстрый sprintf, соотвественно:

M>1) передача размера буффера отпадает, так как придеться постоянно проверять не вышли ли мы за границы буфера, что существенно снизит скорость.
Это мелочь в плане перформанса.

M>Как вам такие варианты ? Может я велосипед изобретаю и уже есть реализации данной задачи ?

Во-первых, вы замеряли общий вклад именно sprintf() и сопутствующих подготовок строк в работу вашего ПО? Что-то мне подсказывает, что вы пытаетесь экономить на спичках. Либо же у вас сильная заточка именно на запись больших объемов текстовых данных. Тогда имеет смысл уйти от sprintf() в сторону чего-то более узкоспециализированного (написать самому либо же взять супер-мега-оптимизированную либу под конкретно эту задачу — писать быстро текст).
Патриот здравого смысла
Re[4]: быстрый sprintf
От: maks1180  
Дата: 01.11.22 12:16
Оценка:
M>Место для локальных переменных выделяется в начале блока, в котором они определены. Если ты, например, в for'е будешь заводить переменные, то никакого непрерывного блока alloca не сможет сделать

Это глупость, так делать не имеет смысла никакого! Посмотри ассемблерный код. Выделяется 1 раз сразу для всех переменных в начале функции.
===============================================
(реклама, удалена модератором)
Отредактировано 01.11.2022 12:20 maks1180 . Предыдущая версия .
Re[5]: быстрый sprintf
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 01.11.22 12:18
Оценка:
Здравствуйте, maks1180, Вы писали:

M>>Место для локальных переменных выделяется в начале блока, в котором они определены. Если ты, например, в for'е будешь заводить переменные, то никакого непрерывного блока alloca не сможет сделать


M>Это глупость! Посмотри ассемблерный код. Выделяется 1 раз сразу для всех переменных в начале функции.


Ну, какой-то компилятор может так себя вести, но я бы на это не закладывался
Маньяк Робокряк колесит по городу
Re[3]: быстрый sprintf
От: · Великобритания  
Дата: 01.11.22 12:21
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Функция которая вызвала будет обрабатывать эту строку, например может записать в файл

fprintf

M>или перекинуть в динамическую память.

sprintf

Ну это сишний подход. В плюсах будут шаблоны/етс. Зачем тут стек — неясно.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[6]: быстрый sprintf
От: maks1180  
Дата: 01.11.22 12:30
Оценка:
M>Ну, какой-то компилятор может так себя вести, но я бы на это не закладывался

Никак компилятор не сможет сделать, так как вы описали.
1) Если после alloca(var), выделить память в стеке, нужно хранить указатель на неё, так как через ebp уже не получиться к ней обращаться.
Т.е. получится ерунда, что-бы выделить место для локальной переменной, нужно ещё где-то выделить место, что-бы хранить указатель на переменную.
2) Это не рационально выделять много раз память в стеке для каждой локальной переменной.
===============================================
(реклама, удалена модератором)
Re: быстрый sprintf
От: kov_serg Россия  
Дата: 01.11.22 15:02
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Как вам такие варианты ?


Для C реализовать функцию
int format_string(const char* format, va_list args, void (*write)(void* ctx),const char* chunk,int chunk_size), void *ctx);

где write(ctx,chunk,chunk_size) записывает фрагмент данных (или просто складывает chunk_size в зависимости от потребностей).
И на её основе сделать все остальные варианты.
Re[2]: быстрый sprintf
От: maks1180  
Дата: 01.11.22 17:58
Оценка:
_>Для C реализовать функцию
_>
_>int format_string(const char* format, va_list args, void (*write)(void* ctx),const char* chunk,int chunk_size), void *ctx);
_>

_>где write(ctx,chunk,chunk_size) записывает фрагмент данных (или просто складывает chunk_size в зависимости от потребностей).
_>И на её основе сделать все остальные варианты.

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

Т.е. выделили мы первый блок Х байт, заполняем его, мы же должны проверять не вышли ли мы за его границы.
При копировании строки заранее неизвестной длины, мы должны делать проверку после записи каждого байта! Думаю такая проверка может снизить скорость в 1.5 раза.
===============================================
(реклама, удалена модератором)
Отредактировано 01.11.2022 18:06 maks1180 . Предыдущая версия . Еще …
Отредактировано 01.11.2022 18:05 maks1180 . Предыдущая версия .
Отредактировано 01.11.2022 18:04 maks1180 . Предыдущая версия .
Отредактировано 01.11.2022 18:01 maks1180 . Предыдущая версия .
Re[3]: быстрый sprintf
От: kov_serg Россия  
Дата: 02.11.22 06:43
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Тут будет выделяться буффер ограниченного размера, когда конечный размер неизвестен, поэтому возвращаемся к началу топика

Тут не будет.
M>"передача размера буффера отпадает, так как придеться постоянно проверять не вышли ли мы за границы буфера, что существенно снизит скорость."
Надо сравнивать конкретную реализацию. Там очень много того что может снижать скорость и это обычно обращение к мимо кэша

M>Т.е. выделили мы первый блок Х байт, заполняем его, мы же должны проверять не вышли ли мы за его границы.

Вы не поняли, можно хоть по одному байту передавать.
M>При копировании строки заранее неизвестной длины, мы должны делать проверку после записи каждого байта! Думаю такая проверка может снизить скорость в 1.5 раза.
Где вы увидели неизвестную длину?
Re[4]: быстрый sprintf
От: maks1180  
Дата: 02.11.22 10:06
Оценка:
M>>При копировании строки заранее неизвестной длины, мы должны делать проверку после записи каждого байта! Думаю такая проверка может снизить скорость в 1.5 раза.
_>Где вы увидели неизвестную длину?

Здесь например, срока p — имеет неизвестную длину
sprintf(buffer, "%s", p);

Посмотрел я реализацию в glibc-2.36 (файл vfprintf-internal.c) там действительно сначало определяют длину строки "p", а потом уже её отдают в _IO_sputn
Получается делают в 2 прохода по строке "p"!
===============================================
(реклама, удалена модератором)
Отредактировано 02.11.2022 11:06 maks1180 . Предыдущая версия . Еще …
Отредактировано 02.11.2022 11:00 maks1180 . Предыдущая версия .
Отредактировано 02.11.2022 10:58 maks1180 . Предыдущая версия .
Отредактировано 02.11.2022 10:57 maks1180 . Предыдущая версия .
Re[5]: быстрый sprintf
От: kov_serg Россия  
Дата: 02.11.22 11:07
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Здесь например, срока p — имеет неизвестную длину

M>sprintf(buffer, "%s", p);
int format_string(const char* format, va_list args, void (*write)(void* ctx),const char* chunk,int chunk_size), void *ctx);

int my_printf(void (*write)(void* ctx),const char* chunk,int chunk_size), void *ctx, const char* format, ...) {
  int res; va_list v; va_start(v,format);
  res=format_string(format,v,write,ctx);
  va_end(v);
  return res;
}

Просто требуем для функции записи фрагмента если chunk_size<0 то chunk это c-string. Тогда можно копировать блоками не вычисляя длину сразу. Хотя такая оптимизация весьма сомнительна.

И потом
my_printf(write_console,console,"%s\t%-16s\t%8s\n",p0,p1,p2);

Если для p0 можно вызвать write(ctx,p0,-1) то для p1 и p2 вам всё равно придётся сначала вычислить длину и в зависимости от неё добавит пробелов слева или справа.

ps: Более того длинна символов не равна количеству байт особенно utf8.
Re: быстрый sprintf
От: McQwerty Россия  
Дата: 02.11.22 11:27
Оценка:
M>Нужно реализовать быстрый sprintf, соотвественно:
M>1) передача размера буффера отпадает, так как придеться постоянно проверять не вышли ли мы за границы буфера, что существенно снизит скорость.

Без профилировки такое утверждать весьма тяжело.
Re[6]: быстрый sprintf
От: maks1180  
Дата: 02.11.22 12:08
Оценка:
_>Если для p0 можно вызвать write(ctx,p0,-1) то для p1 и p2 вам всё равно придётся сначала вычислить длину и в зависимости от неё добавит пробелов слева или справа.
Достаточно углубиться не более чем на 8 и 16 символов для p1 и p2
Точнее, если нам нужно напечать строку слева, то её печатаем и одновременно узнаём её длину.
===============================================
(реклама, удалена модератором)
Отредактировано 02.11.2022 12:31 maks1180 . Предыдущая версия .
Re[2]: быстрый sprintf
От: maks1180  
Дата: 02.11.22 12:11
Оценка:
M>>1) передача размера буффера отпадает, так как придеться постоянно проверять не вышли ли мы за границы буфера, что существенно снизит скорость.

MQ>Без профилировки такое утверждать весьма тяжело.


Почему ? Дополнительная проверка всегда приводит к снижению скорости. Разве это не очевидно ?
===============================================
(реклама, удалена модератором)
Re[3]: быстрый sprintf
От: kov_serg Россия  
Дата: 02.11.22 12:21
Оценка: 9 (1)
Здравствуйте, maks1180, Вы писали:

MQ>>Без профилировки такое утверждать весьма тяжело.

M>Почему ? Дополнительная проверка всегда приводит к снижению скорости. Разве это не очевидно ?

Вообще-то нет. Не всё так просто как хотелось бы.

https://gist.github.com/hellerbarde/2843375

https://alvinalexander.com/sites/default/files/2017-07/not-all-cpu-operations-equals.png
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.