Есть ли способ выделить стандартный массив Rust прямо в кучу, полностью пропуская стек?

Question

В Stack Overflow уже есть несколько вопросов о выделении массива (скажем, [i32]) в куче.Общая рекомендация - бокс, например Box<[i32]>.Но хотя бокс работает достаточно хорошо для небольших массивов, проблема в том, что упаковываемый массив должен сначала располагаться в стеке.

Так что, если массив слишком большой (скажем, 10 миллионов элементов), вы будете -даже с боксом - получите переполнение стека (маловероятно, что у вас будет такой большой стек).

Вместо этого предлагается использовать Vec<T>, то есть Vec<i32> в нашем примере.И хотя это делает свою работу, это оказывает влияние на производительность.

Рассмотрим следующую программу:

fn main() {
    const LENGTH: usize = 10_000;
    let mut a: [i32; LENGTH] = [0; LENGTH];
    for j in 0..LENGTH {
        for i in 0..LENGTH {
            a[i] = j as i32;
        }
    }
}

time говорит мне, что запуск этой программы занимает около 2,9 секунды.В этом примере я использую 10'000, поэтому могу выделить его в стеке, но я действительно хочу один с 10 млн.

Теперь рассмотрим ту же программу, но с Vec<T> вместо:

fn main() {
    const LENGTH: usize = 10_000;
    let mut a: Vec<i32> = vec![0; LENGTH];
    for j in 0..LENGTH {
        for i in 0..LENGTH {
            a[i] = j as i32;
        }
    }
}

time говорит мне, что запуск этой программы занимает около 5 секунд.Теперь time не является сверхточным, но разница в 2 секунды для такой простой программы не имеет существенного значения.

Хранилище - это хранилище, программа с массивом работает так же быстро, когда массивв штучной упаковке.Так что это не куча, замедляющая версию Vec<T>, а сама структура Vec<T>.

Я также пытался использовать HashMap (в частности, HashMap<usize, i32> для имитации структуры массива), но это далекомедленнее, чем решение Vec<T>.

Если бы мои LENGTH были 10 миллионов, первая версия даже не запустилась бы.

Если это невозможно, существует ли структура, котораяведет себя как массив (и Vec<T>) в куче, но может соответствовать скорости и производительности массива?

Answer 1

Если вам действительно нужен массив, выделенный в куче, т.е. Box<[i32; LENGTH]>, тогда вы можете использовать:

fn main() {
    const LENGTH: usize = 10_000_000;

    let mut a = {
        let mut v: Vec<i32> = Vec::with_capacity(LENGTH);

        // Explicitly set length which is safe since the allocation is
        // sized correctly.
        unsafe { v.set_len(LENGTH); };

        // While not required for this particular example, in general
        // we want to initialize elements to a known value.
        let mut slice = v.into_boxed_slice();
        for i in &mut slice[..] {
            *i = 0;
        }

        let raw_slice = Box::into_raw(slice);

        // Using `from_raw` is safe as long as the pointer is
        // retrieved using `into_raw`.
        unsafe {
            Box::from_raw(raw_slice as *mut [i32; LENGTH])
        }
    };

    // This is the micro benchmark from the question.
    for j in 0..LENGTH {
        for i in 0..LENGTH {
            a[i] = j as i32;
        }
    }
}

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

Answer 2

Резюме : ваш эталонный тест имеет недостатки;просто используйте Vec (как описано здесь ), возможно, с into_boxed_slice, поскольку это невероятно маловероятно, что он будет медленнее, чем выделенный массив кучи.

---

К сожалению, ваши тесты неверны.Прежде всего, вы, вероятно, не компилировали с оптимизациями (--release для груза, -O для rustc).Потому что, если бы вы имели, компилятор Rust удалил бы весь ваш код.См. сборку здесь .Зачем?Поскольку вы никогда не наблюдаете вектор / массив, поэтому нет необходимости выполнять всю эту работу в первую очередь.

Кроме того, ваш тест не проверяет то, что вы действительно хотите проверить.Вы сравниваете массив, выделенный стеком, с вектором, выделенным в куче.Вы должны сравнить Vec с массивом, выделенным для кучи.

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

---

Я исправил ваш тест и включил все три возможности: Vec, массив в стеке и массив в куче.Вы можете найти полный код здесь .Результаты:

running 3 tests
test array_heap  ... bench:   9,600,979 ns/iter (+/- 1,438,433)
test array_stack ... bench:   9,232,623 ns/iter (+/- 720,699)
test vec_heap    ... bench:   9,259,912 ns/iter (+/- 691,095)

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

Обратите внимание, что этот тест все еще довольно плох.Два цикла можно просто заменить одним циклом, установив для всех элементов массива значение LENGTH - 1.Из-за быстрого взгляда на сборку (и из-за довольно продолжительного времени в 9 мс) я думаю, что LLVM недостаточно умен, чтобы фактически выполнить эту оптимизацию.Но такие вещи важны, и об этом следует помнить.

---

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

Секция данных Vec<T> имеет точно такую ​​же структуру памяти, что и [T]: просто много T с непрерывно в памяти.Супер просто.Это также означает, что оба демонстрируют одинаковое поведение кэширования (в частности, очень удобное для кэширования).

Единственное отличие состоит в том, что Vec может иметь больше возможностей, чем элементы.Так что Vec сам хранит (pointer, length, capacity).Это на одно слово больше, чем простой (в штучной упаковке) фрагмент (который хранит (pointer, length)).Массив в штучной упаковке не должен хранить длину, поскольку он уже находится в типе, так что это просто простой указатель.Неважно, будем ли мы хранить одно, два или три слова, если у вас все равно будут миллионы элементов.

Доступ к одному элементу одинаков для всех трех: сначала мы выполняем проверку границ, а затем вычисляем целевой указатель с помощью base_pointer + size_of::<T>() * index.Но важно отметить, что массив, хранящий свою длину в типе, означает, что оптимизатор может легче удалить проверку границ!Это может быть реальным преимуществом.

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