<commit_before>/*******************************************************************************
 * include/huffman/huff_dd.hpp
 *
 * Copyright (C) 2017 <NAME> <<EMAIL>>
 * Copyright (C) 2017 <NAME> <<EMAIL>>
 *
 * All rights reserved. Published under the BSD-2 license in the LICENSE file.
 ******************************************************************************/

#pragma once

#include <algorithm>
#include <cstring>
#include <omp.h>
#include <vector>

#include "construction/wavelet_structure.hpp"
#include "arrays/slice.hpp"

#include "huffman/huff_merge.hpp"
#include "huffman/huff_bit_vectors.hpp"
#include "huffman/huff_codes.hpp"
#include "huffman/ctx_huff_all_levels.hpp"
#include "huffman/huff_parallel_level_sizes_builder.hpp"

template <typename Algorithm, typename AlphabetType, bool is_tree_>
class huff_dd {

public:
  static constexpr bool  is_parallel = true;
  static constexpr bool  is_tree   = is_tree_;
  static constexpr uint8_t word_width  = sizeof(AlphabetType);
  static constexpr bool  is_huffman_shaped = true;

  using ctx_t = ctx_huff_all_levels<is_tree>;

  template <typename InputType>
  static wavelet_structure compute(const InputType& global_text_ptr,
    const uint64_t size, const uint64_t /*levels*/) {

    // TODO ^ remove levels parameter from API

    Slice<AlphabetType const> const global_text { global_text_ptr, size };

    const uint64_t shards = omp_get_max_threads();

    std::vector<histogram<AlphabetType>> local_hists(shards);

    auto get_local_slice = [size, shards] (size_t rank, auto slice) {
      const uint64_t offset = (rank * (size / shards)) +
        std::min<uint64_t>(rank, size % shards);
      const uint64_t local_size = (size / shards) +
        ((rank < size % shards) ? 1 : 0);

      return slice.slice(offset, offset + local_size);
    };

    #pragma omp parallel for
    for (size_t shard = 0; shard < shards; shard++) {
      auto text = get_local_slice(shard, global_text);

      // calculate local histogram
      local_hists[shard] = histogram<AlphabetType>(text.data(), text.size());
    }

    // merge local histograms
    histogram<AlphabetType> merged_hist(local_hists);

    // prepare level size builder
    auto builder = parallel_level_sizes_builder<AlphabetType> {
        std::move(merged_hist),
        std::move(local_hists),
    };

    // build huffman codes and calculate level sizes
    canonical_huff_codes<AlphabetType, is_tree> codes
      = canonical_huff_codes<AlphabetType, is_tree>(builder);
    uint64_t const levels = builder.levels();

    if(size == 0) {
      if constexpr (ctx_t::compute_zeros) {
        return wavelet_structure_matrix_huffman(std::move(codes));
      } else {
        return wavelet_structure_tree_huffman(std::move(codes));
      }
    }

    const auto rho = rho_dispatch<is_tree>::create(levels);
    auto ctxs = std::vector<ctx_t>(shards);

    // NB: Only allocate if needed
    std::vector<AlphabetType> global_sorted_text_allocation;
    if constexpr (Algorithm::needs_second_text_allocation) {
      global_sorted_text_allocation = std::vector<AlphabetType>(size);
    }
    Slice<AlphabetType> const global_sorted_text {
        global_sorted_text_allocation.data(),
        global_sorted_text_allocation.size()
    };

    #pragma omp parallel for
    for (size_t shard = 0; shard < shards; shard++) {
      std::vector<uint64_t> const& local_level_sizes
        = builder.level_sizes_shards()[shard];

      auto const text = get_local_slice(shard, global_text);

      ctxs[shard] = ctx_t(local_level_sizes, levels, rho);
<commit_msg>Rename Slice -> span<commit_after>/*******************************************************************************
 * include/huffman/huff_dd.hpp
 *
 * Copyright (C) 2017 <NAME> <<EMAIL>>
 * Copyright (C) 2017 <NAME> <<EMAIL>>
 *
 * All rights reserved. Published under the BSD-2 license in the LICENSE file.
 ******************************************************************************/

#pragma once

#include <algorithm>
#include <cstring>
#include <omp.h>
#include <vector>

#include "construction/wavelet_structure.hpp"
#include "arrays/span.hpp"

#include "huffman/huff_merge.hpp"
#include "huffman/huff_bit_vectors.hpp"
#include "huffman/huff_codes.hpp"
#include "huffman/ctx_huff_all_levels.hpp"
#include "huffman/huff_parallel_level_sizes_builder.hpp"

template <typename Algorithm, typename AlphabetType, bool is_tree_>
class huff_dd {

public:
  static constexpr bool  is_parallel = true;
  static constexpr bool  is_tree   = is_tree_;
  static constexpr uint8_t word_width  = sizeof(AlphabetType);
  static constexpr bool  is_huffman_shaped = true;

  using ctx_t = ctx_huff_all_levels<is_tree>;

  template <typename InputType>
  static wavelet_structure compute(const InputType& global_text_ptr,
    const uint64_t size, const uint64_t /*levels*/) {

    // TODO ^ remove levels parameter from API

    span<AlphabetType const> const global_text { global_text_ptr, size };

    const uint64_t shards = omp_get_max_threads();

    std::vector<histogram<AlphabetType>> local_hists(shards);

    auto get_local_slice = [size, shards] (size_t rank, auto slice) {
      const uint64_t offset = (rank * (size / shards)) +
        std::min<uint64_t>(rank, size % shards);
      const uint64_t local_size = (size / shards) +
        ((rank < size % shards) ? 1 : 0);

      return slice.slice(offset, offset + local_size);
    };

    #pragma omp parallel for
    for (size_t shard = 0; shard < shards; shard++) {
      auto text = get_local_slice(shard, global_text);

      // calculate local histogram
      local_hists[shard] = histogram<AlphabetType>(text.data(), text.size());
    }

    // merge local histograms
    histogram<AlphabetType> merged_hist(local_hists);

    // prepare level size builder
    auto builder = parallel_level_sizes_builder<AlphabetType> {
        std::move(merged_hist),
        std::move(local_hists),
    };

    // build huffman codes and calculate level sizes
    canonical_huff_codes<AlphabetType, is_tree> codes
      = canonical_huff_codes<AlphabetType, is_tree>(builder);
    uint64_t const levels = builder.levels();

    if(size == 0) {
      if constexpr (ctx_t::compute_zeros) {
        return wavelet_structure_matrix_huffman(std::move(codes));
      } else {
        return wavelet_structure_tree_huffman(std::move(codes));
      }
    }

    const auto rho = rho_dispatch<is_tree>::create(levels);
    auto ctxs = std::vector<ctx_t>(shards);

    // NB: Only allocate if needed
    std::vector<AlphabetType> global_sorted_text_allocation;
    if constexpr (Algorithm::needs_second_text_allocation) {
      global_sorted_text_allocation = std::vector<AlphabetType>(size);
    }
    span<AlphabetType> const global_sorted_text {
        global_sorted_text_allocation.data(),
        global_sorted_text_allocation.size()
    };

    #pragma omp parallel for
    for (size_t shard = 0; shard < shards; shard++) {
      std::vector<uint64_t> const& local_level_sizes
        = builder.level_sizes_shards()[shard];

      auto const text = get_local_slice(shard, global_text);

      ctxs[shard] = ctx_t(local_level_sizes, levels, rho);

{'fraction_non_alphanumeric': 0.14751812604573342, 'fraction_numerical': 0.00864472950362521, 'mean_word_length': 4.119914346895075, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 60, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7457742', 'n_tokens_mistral': 2398, 'n_tokens_neox': 2255, 'n_words': 508}