Блог

Представьте, что вы анализируете строку и хотите извлечь подстроку. Чтобы представить эту подстроку, я вижу два способа:

 // 1. represent it using a start pointer and a length
struct { char *start; size_t length; };
// 2. represent it using two pointers, start and end
struct { char *start; char *end; };

// or it could as well be returned by a function:
char *find_substring(char *s, size_t s_len, size_t *substring_len);
char *find_substring(char *s, size_t s_len, char **substring_end);
  

Есть ли причина предпочесть одну форму другой? Это зависит только от настроек? Я не вижу, чтобы это влияло на производительность, поскольку одно может быть переведено в другое с помощью простого сложения / вычитания, но я могу ошибаться.

Контекст — это анализатор HTTP-запроса, если это что-то меняет. Я использовал первый, но мне любопытно, вносит ли второй что-нибудь в таблицу, поскольку я видел, что он используется в picohttpparser.

Есть ли причина предпочесть одну форму другой?

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

Если чаще добавлять данные в конце, то *end будет быстрее start[length ] .

Если чаще вы получаете длину строки, тогда просто length будет быстрее end - start .

Помните о правилах оптимизации. Единственный реальный ответ приходит от профилирования вашего кода.

Это зависит только от настроек?

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

Мы могли бы также проверить существующие реализации. В C все (все?) Стандартные функции C и в POSIX, такие как strbuf, aiocb, очереди сообщений XSI, iovec используют указатель целое число для представления области памяти. Я думаю, что все реализации C std::vector , такие как glibc std::vector или llvm vector, используют указатели внутри, но можно ожидать, что они будут оптимизированы для push_back() операций.

Обычно я склоняюсь к использованию указателей. При работе с size_t вами приходится обрабатывать переполнение и переполнение, а также отрицательные / слишком большие значения или преобразование из разности указателей ptrdiff_t в size_t . Такие проблемы исчезают с указателями — указатель либо действителен, либо нет, вам нужно только проверить привязку с помощью < > операторов, можете ли вы увеличить / уменьшить его или нет. Однако при написании внешнего API я бы использовал size_t , поскольку программисты на C используются для представления области памяти с использованием этого соглашения.

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

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

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

Второй способ пропускает информацию о внутреннем представлении строки, в то время как первый этого не делает.