cp-algo/util/big_alloc.hpp

• View this file on GitHub
• Last update: 2025-04-26 12:30:09+02:00
• Include: #include "cp-algo/util/big_alloc.hpp"

Required by

• cp-algo/linalg/frobenius.hpp
• cp-algo/math/cvector.hpp
• cp-algo/math/fft.hpp
• cp-algo/math/poly.hpp
• cp-algo/math/poly/impl/div.hpp
• cp-algo/math/poly/impl/euclid.hpp

Verified with

• Characteristic Polynomial (verify/linalg/characteristic.test.cpp)
• Pow of Matrix (Frobenius) (verify/linalg/pow_fast.test.cpp)
• Bell Number (verify/poly/bell.test.cpp)
• Convolution mod $10^9+7$ (verify/poly/convolution107.test.cpp)
• Division of Polynomials (verify/poly/div.test.cpp)
• Exp of Power Series (verify/poly/exp.test.cpp)
• Find Linear Recurrence (verify/poly/find_linrec.test.cpp)
• Polynomial Interpolation (verify/poly/inter.test.cpp)
• Polynomial Interpolation (Geometric Sequence) (verify/poly/inter_geo.test.cpp)
• Inv of Power Series (verify/poly/inv.test.cpp)
• Inv of Polynomials (verify/poly/inv_mod.test.cpp)
• Consecutive Terms of Linear Recursion (verify/poly/linrec_consecutive.test.cpp)
• Kth term of Linearly Recurrent Sequence (verify/poly/linrec_single.test.cpp)
• Log of Power Series (verify/poly/log.test.cpp)
• Multipoint Evaluation (verify/poly/multieval.test.cpp)
• Multipoint Evaluation (Geometric Sequence) (verify/poly/multieval_geo.test.cpp)
• Pow of Power Series (verify/poly/pow.test.cpp)
• Product of Polynomial Sequence (verify/poly/prod_sequence.test.cpp)
• Polynomial Root Finding (verify/poly/roots.test.cpp)
• Shift of Sampling Points of Polynomial (verify/poly/sampling.test.cpp)
• Sqrt of Power Series (verify/poly/sqrt.test.cpp)
• Polynomial Taylor Shift (verify/poly/taylor.test.cpp)
• Wildcard Pattern Matching (verify/poly/wildcard.test.cpp)

Code

#ifndef CP_ALGO_UTIL_big_alloc_HPP
#define CP_ALGO_UTIL_big_alloc_HPP

#include <cstddef>
#include <iostream>

// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#  define CP_ALGO_USE_MMAP 1
#  include <sys/mman.h>
#else
#  define CP_ALGO_USE_MMAP 0
#endif

namespace cp_algo {
    template <typename T>
    class big_alloc: public std::allocator<T> {
        public:
        using value_type = T;
        using base = std::allocator<T>;

        big_alloc() noexcept = default;

        template <typename U>
        big_alloc(const big_alloc<U>&) noexcept {}

#if CP_ALGO_USE_MMAP
        [[nodiscard]] T* allocate(std::size_t n) {
            if(n * sizeof(T) < 1024 * 1024) {
                return base::allocate(n);
            }
            n *= sizeof(T);
            void* raw = mmap(nullptr, n,
                            PROT_READ | PROT_WRITE,
                            MAP_PRIVATE | MAP_ANONYMOUS,
                            -1, 0);
            madvise(raw, n, MADV_HUGEPAGE);
            madvise(raw, n, MADV_POPULATE_WRITE);
            return static_cast<T*>(raw);
        }
#endif

#if CP_ALGO_USE_MMAP
        void deallocate(T* p, std::size_t n) noexcept {
            if(n * sizeof(T) < 1024 * 1024) {
                return base::deallocate(p, n);
            }
            if(p) {
                munmap(p, n * sizeof(T));
            }
        }
#endif
    };
}
#endif // CP_ALGO_UTIL_big_alloc_HPP

#line 1 "cp-algo/util/big_alloc.hpp"



#include <cstddef>
#include <iostream>

// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#  define CP_ALGO_USE_MMAP 1
#  include <sys/mman.h>
#else
#  define CP_ALGO_USE_MMAP 0
#endif

namespace cp_algo {
    template <typename T>
    class big_alloc: public std::allocator<T> {
        public:
        using value_type = T;
        using base = std::allocator<T>;

        big_alloc() noexcept = default;

        template <typename U>
        big_alloc(const big_alloc<U>&) noexcept {}

#if CP_ALGO_USE_MMAP
        [[nodiscard]] T* allocate(std::size_t n) {
            if(n * sizeof(T) < 1024 * 1024) {
                return base::allocate(n);
            }
            n *= sizeof(T);
            void* raw = mmap(nullptr, n,
                            PROT_READ | PROT_WRITE,
                            MAP_PRIVATE | MAP_ANONYMOUS,
                            -1, 0);
            madvise(raw, n, MADV_HUGEPAGE);
            madvise(raw, n, MADV_POPULATE_WRITE);
            return static_cast<T*>(raw);
        }
#endif

#if CP_ALGO_USE_MMAP
        void deallocate(T* p, std::size_t n) noexcept {
            if(n * sizeof(T) < 1024 * 1024) {
                return base::deallocate(p, n);
            }
            if(p) {
                munmap(p, n * sizeof(T));
            }
        }
#endif
    };
}

Back to top page