FPS の作業領域

components/fps_workspace.hpp · GitHub で見る

共通ページ

FPS 内部で使う、64 byte 以上に整列した unsigned int の作業領域です。

操作	内容・返り値	計算量
fps_detail::allocate_fps_words(n)	n ワードの作業領域の所有権を返す	OS・アロケータに依存
storage[i]	i 番目のワードへの参照	\(O(1)\)
storage.get()	先頭ワードへのポインタ	\(O(1)\)

#include "lib/components/fps_workspace.hpp"

auto storage = fps_detail::allocate_fps_words(1024);
storage[0] = 1;

FpsWords は所有権を移動できる配列です。要素の初期値は未規定で、使用前に書き込む必要があります。

Linux では 2 MiB 以上の要求に対し、2 MiB 境界に整列した匿名マッピングと MADV_HUGEPAGE を使います。大きなページの利用は OS の設定と資源に依存します。マッピングに失敗した場合と他の環境では、通常の整列した配列確保に戻ります。確保できなければ std::bad_alloc を送出します。解放方法は所有する配列が保持します。

大きなページ用のマッピングは要求を 2 MiB 単位に切り上げ、整列のためにさらに 2 MiB の仮想アドレス領域を確保します。

計算量: 作業領域は \(O(n)\) です。確保と解放の時間は OS とアロケータに依存します。

検証コード

• test/convolution.test.cpp
• test/convolution.test.cpp
• test/cyclic_convolution.test.cpp
• test/fps_bostan_mori.test.cpp
• test/fps_bostan_mori.test.cpp
• test/fps_compose.test.cpp
• test/fps_compose.test.cpp
• test/fps_compose_large.test.cpp
• test/fps_compose_large.test.cpp
• test/fps_compositional_inverse.test.cpp
• test/fps_compositional_inverse.test.cpp
• test/fps_compositional_inverse_large.test.cpp
• test/fps_compositional_inverse_large.test.cpp
• test/fps_divmod.test.cpp
• test/fps_divmod.test.cpp
• test/fps_exp.test.cpp
• test/fps_exp.test.cpp
• test/fps_exp_sparse.test.cpp
• test/fps_exp_sparse.test.cpp
• test/fps_interpolate.test.cpp
• test/fps_interpolate.test.cpp
• test/fps_inv.test.cpp
• test/fps_inv.test.cpp
• test/fps_inv_sparse.test.cpp
• test/fps_inv_sparse.test.cpp
• test/fps_linear_recurrence.test.cpp
• test/fps_linear_recurrence.test.cpp
• test/fps_log.test.cpp
• test/fps_log.test.cpp
• test/fps_log_sparse.test.cpp
• test/fps_log_sparse.test.cpp
• test/fps_pow.test.cpp
• test/fps_pow.test.cpp
• test/fps_pow_sparse.test.cpp
• test/fps_pow_sparse.test.cpp
• test/fps_rational_coefficients.test.cpp
• test/fps_rational_coefficients.test.cpp
• test/fps_sqrt.test.cpp
• test/fps_sqrt.test.cpp
• test/fps_sqrt_sparse.test.cpp
• test/fps_sqrt_sparse.test.cpp
• test/fps_taylor_shift.test.cpp
• test/fps_taylor_shift.test.cpp
• test/multiplicative_convolution.test.cpp
• test/multipoint_eval.test.cpp
• test/multipoint_eval.test.cpp
• test/multivariate_convolution.test.cpp
• test/ordered_convolution.test.cpp
• test/polynomial_inv_mod.test.cpp
• test/polynomial_inv_mod.test.cpp
• test/power_projection.test.cpp
• test/power_projection.test.cpp

コード

#ifndef CP_COMPONENTS_FPS_WORKSPACE_HPP
#define CP_COMPONENTS_FPS_WORKSPACE_HPP

#include <cstddef>
#include <cstdint>
#include <limits>
#include <memory>
#include <new>
#if defined(__linux__)
#include <sys/mman.h>
#endif

namespace fps_detail {

struct FpsWordsDelete {
	void *region = nullptr;
	std::size_t bytes = 0;
	void operator()(unsigned int *p) const {
#if defined(__linux__)
		if (region) {
			munmap(region, bytes);
			return;
		}
#endif
		::operator delete[](p, std::align_val_t(64));
	}
};

using FpsWords = std::unique_ptr<unsigned int[], FpsWordsDelete>;

inline FpsWords allocate_fps_words(std::size_t count) {
#if defined(__linux__) && defined(MADV_HUGEPAGE)
	constexpr std::size_t page = 1 << 21;
	if (count >= page / sizeof(unsigned int) &&
		count <= (std::numeric_limits<std::size_t>::max() - 2 * page) / sizeof(unsigned int)) {
		const std::size_t bytes = (count * sizeof(unsigned int) + page - 1) / page * page;
		void *region = mmap(nullptr, bytes + page, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
		if (region != MAP_FAILED) {
			const auto address = (reinterpret_cast<std::uintptr_t>(region) + page - 1) & ~(page - 1);
			auto *p = ::new (reinterpret_cast<void *>(address)) unsigned int[count];
			madvise(p, bytes, MADV_HUGEPAGE);
			return FpsWords(p, FpsWordsDelete{region, bytes + page});
		}
	}
#endif
	return FpsWords(new (std::align_val_t(64)) unsigned int[count]);
}

}

#endif

Back to top page