Как улучшить производительность динамического массива, реализованного с помощью void **? - PullRequest
0 голосов
/ 20 октября 2018

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

Сейчас моя реализация void** на ~ 50% медленнее, чем использование int* напрямую:

#define N 1000000000

// Takes ~6 seconds
void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        *(int*)(&a[i]) = i;

}
printf("%d\n", *(int*)&a[N-1]);

// Takes ~3 seconds
int* b = malloc(sizeof(int) * N) ;
for (int i =0; i < N; i++) {
        b[i] = i;
}
printf("%d\n", b[N-1]);

Я не эксперт по Си.Есть ли лучший способ сделать это?

Спасибо

edit

Похоже, использование void** - плохая идея.Есть ли способ реализовать это с помощью void*?

Вот как это реализовано в Go:

type slice struct {
        array unsafe.Pointer
        len   int
        cap   int
}

Я бы хотел сделать что-то подобное.

edit2

Мне удалось реализовать это с помощью void*.

Решение было действительно простым:

 void* a = malloc(sizeof(int) * N);
 for (int i = 0; i < N; i++) {
    ((int*)a)[i] = i;
 }
 printf("%d\n", ((int*)a)[N-1]);

Производительность теперь такая же.

Ответы [ 3 ]

0 голосов
/ 20 октября 2018

Имейте в виду, что sizeof(void *) является удвоенным значением sizeof(int) на 64-битных процессорах (адрес 8 байтов против целого числа 4 байта со знаком).Если это ваш случай, могу поспорить, что разница только в пропуске кэша страниц.Ваш блок памяти требуется для загрузки в два раза больше страниц, что является медленным ( ссылка для получения дополнительной информации здесь ).

Обратите также внимание, что векторы C ++ не являются "динамическим массивом, который может работатьс любым типом ".Они связаны с типом, например: std::vector<int> - это динамический массив, но в котором вы можете хранить только int.

. Решением вашей проблемы может быть реализация некоторого вида std::vector<void *> в CНо это не эффективно.

  • Вам нужно сделать 2 выделения для каждого элемента (1 для контейнера и 1 для самого элемента)
  • Вам нужно делать 2 уровня косвенности при каждом доступе к данным(1 для получения указателя в контейнере и 1 для получения данных в элементе)
  • Вам необходимо хранить некоторую информацию о типе в каждом элементе.Если нет, вы не знаете, что находится в вашем динамическом массиве
0 голосов
/ 20 октября 2018

Мне удалось реализовать это с помощью void*.

Решение было действительно простым:

 void* a = malloc(sizeof(int) * N);
 for (int i =0;i<N;i++) {
  ((int*)a)[i] = i;
 }
 printf("%d\n", ((int*)a)[N-1]);

Производительность теперь такая же.

Я тоже сталкивалсяЭта замечательная статья, которая объясняет, как реализовать общую структуру данных в C:

http://jiten -thakkar.com / posts / writing-generic-stack-in-c

0 голосов
/ 20 октября 2018

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

Ваш первый код можно исправить, в некотором смысле, например:

void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        a[i] = (void *) i;

}
printf("%d\n", (int) a[N-1]);

Это основано на том факте, что C допускает преобразования между указателем и целочисленным типом (хотя и не обязательно без потери данных), и обратите внимание, что существует только один уровень косвенности (индексация массива), а не два.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...