Project
Loading...
Searching...
No Matches
DenseHistogram.h
Go to the documentation of this file.
1// Copyright 2019-2023 CERN and copyright holders of ALICE O2.
2// See https://alice-o2.web.cern.ch/copyright for details of the copyright holders.
3// All rights not expressly granted are reserved.
4//
5// This software is distributed under the terms of the GNU General Public
6// License v3 (GPL Version 3), copied verbatim in the file "COPYING".
7//
8// In applying this license CERN does not waive the privileges and immunities
9// granted to it by virtue of its status as an Intergovernmental Organization
10// or submit itself to any jurisdiction.
11
15
16#ifndef RANS_INTERNAL_CONTAINERS_DENSEHISTOGRAM_H_
17#define RANS_INTERNAL_CONTAINERS_DENSEHISTOGRAM_H_
18
19#include <algorithm>
20#include <cassert>
21
22#include <gsl/span>
23
24#include <fairlogger/Logger.h>
25#include <utility>
26
32
33#ifdef RANS_SIMD
36
37#ifdef RANS_OPENMP
38#include <omp.h>
39#endif
40
41#endif /* RANS_SIMD */
42
43namespace o2::rans
44{
45
46namespace internal
47{
48namespace histogramImpl
49{
50
51template <typename source_T>
52inline std::pair<source_T, source_T> minmaxImpl(const source_T* begin, const source_T* end)
53{
54 const auto [minIter, maxIter] = std::minmax_element(begin, end);
55 return {*minIter, *maxIter};
56};
57
58#ifdef RANS_SIMD
59template <>
60inline std::pair<uint32_t, uint32_t> minmaxImpl<uint32_t>(const uint32_t* begin, const uint32_t* end)
61{
62 return internal::simd::minmax(begin, end);
63};
64
65template <>
66inline std::pair<int32_t, int32_t> minmaxImpl<int32_t>(const int32_t* begin, const int32_t* end)
67{
68 return internal::simd::minmax(begin, end);
69};
70#endif /* RANS_SIMD */
71
72}; // namespace histogramImpl
73
74template <typename source_T>
75inline std::pair<source_T, source_T> minmax(gsl::span<const source_T> range)
76{
77 const auto begin = range.data();
78 const auto end = begin + range.size();
79 return histogramImpl::minmaxImpl<source_T>(begin, end);
80};
81
82} // namespace internal
83
84namespace utils
85{
86template <typename source_T>
87inline std::pair<source_T, source_T> minmax(gsl::span<const source_T> range)
88{
89 return internal::minmax(range);
90}
91} // namespace utils
92
93template <typename source_T, typename = void>
94class DenseHistogram;
95
96template <typename source_T>
97class DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>> : public internal::VectorContainer<source_T, uint32_t>,
98 public internal::HistogramConcept<source_T,
99 typename internal::VectorContainer<source_T, uint32_t>::value_type,
100 typename internal::VectorContainer<source_T, uint32_t>::difference_type,
101 DenseHistogram<source_T>>
102{
108
109 friend containerBase_type;
111
112 public:
123
124 DenseHistogram() = default;
125
126 template <typename freq_IT>
128
129 // operations
130 using HistogramConcept_type::addSamples;
131
132 using HistogramConcept_type::addFrequencies;
133
134 template <typename source_IT>
136 {
137 if constexpr (std::is_pointer_v<source_IT>) {
138 return addSamplesImpl(gsl::make_span(begin, end), min, max);
139 } else {
140 return addSamplesImpl(begin, end, min, max);
141 }
142 };
143
144 template <typename source_IT>
145 DenseHistogram& addSamples(gsl::span<const source_type> span, source_type min, source_type max)
146 {
147 return addSamplesImpl(span, min, max);
148 };
149
151
153 {
154 return resize(this->getOffset(), this->getOffset() + newSize);
155 };
156
157 protected:
158 DenseHistogram& addSamplesImpl(gsl::span<const source_type> span);
159
160 template <typename source_IT>
161 DenseHistogram& addSamplesImpl(source_IT begin, source_IT end);
162
163 template <typename source_IT>
165
166 DenseHistogram& addSamplesImpl(gsl::span<const source_type> span, source_type min, source_type max);
167
168 template <typename freq_IT>
170
171 private:
172 inline static constexpr size_t MaxSize{utils::pow2(30)}; // 4GB per histogram size limit;
173
174 bool isValidRange(difference_type min, difference_type max);
175};
176
177template <typename source_T>
178inline bool DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::isValidRange(difference_type min, difference_type max)
179{
180 bool ret = true;
181 if constexpr (std::is_unsigned_v<source_T>) {
182 if (min < 0) {
183 LOGP(warning, "trying to add frequencies for a signed symbol to a DenseHistogram of an unsiged type.");
184 ret = false;
185 }
186 }
187 if (max - min > static_cast<difference_type>(this->MaxSize)) {
188 LOGP(warning, "DenseHistogram exceeds {} elements threshold", this->MaxSize);
189 ret = false;
190 }
191 return ret;
192}
193
194template <typename source_T>
195inline auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::addSamplesImpl(gsl::span<const source_type> samples) -> DenseHistogram&
196{
197 if (samples.size() > 0) {
198 const auto [min, max] = internal::minmax(samples);
199 addSamplesImpl(samples, min, max);
200 } else {
201 LOG(warning) << "Passed empty message to " << __func__; // RS this is ok for empty columns
202 }
203 return *this;
204}
205
206template <typename source_T>
207template <typename source_IT>
208inline auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::addSamplesImpl(source_IT begin, source_IT end) -> DenseHistogram&
209{
210 if (begin != end) {
211 const auto [minIter, maxIter] = std::minmax_element(begin, end);
212 addSamplesImpl(begin, end, *minIter, *maxIter);
213 } else {
214 LOG(warning) << "Passed empty message to " << __func__; // RS this is ok for empty columns
215 }
216 return *this;
217}
218
219template <typename source_T>
220inline auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::addSamplesImpl(gsl::span<const source_type> samples, source_type min, source_type max) -> DenseHistogram&
221{
222 using namespace internal;
223 using namespace utils;
224
225 if (samples.empty()) {
226 return *this;
227 }
228 this->resize(min, max);
229
230 const auto begin = samples.data();
231 const auto end = begin + samples.size();
232 constexpr size_t ElemsPerQWord = sizeof(uint64_t) / sizeof(source_type);
233 constexpr size_t nUnroll = 4 * ElemsPerQWord;
234 auto iter = begin;
235
236 if (getRangeBits(min, max) <= 17) {
237 container_type histogram{this->mContainer.size(), this->mContainer.getOffset()};
238
239 auto addQWord = [&, this](uint64_t in64) {
240 uint64_t i = in64;
241 ++this->mContainer[static_cast<source_type>(i)];
242 i = in64 >> 32;
243 ++histogram[static_cast<source_type>(i)];
244 };
245
246 if (end - nUnroll > begin) {
247 for (; iter < end - nUnroll; iter += nUnroll) {
248 addQWord(load64(iter));
249 addQWord(load64(iter + ElemsPerQWord));
250 addQWord(load64(iter + 2 * ElemsPerQWord));
251 addQWord(load64(iter + 3 * ElemsPerQWord));
252 this->mNSamples += nUnroll;
253 __builtin_prefetch(iter + 512, 0);
254 }
255 }
256
257 while (iter != end) {
258 ++this->mNSamples;
259 ++this->mContainer[*iter++];
260 }
261#if defined(RANS_OPENMP) && defined(RANS_SIMD)
262#pragma omp simd
263#endif
264 for (size_t i = 0; i < this->size(); ++i) {
265 this->mContainer.data()[i] += histogram.data()[i];
266 }
267 } else {
268 auto addQWord = [&, this](uint64_t in64) {
269 uint64_t i = in64;
270 ++this->mContainer[static_cast<source_type>(i)];
271 i = in64 >> 32;
272 ++this->mContainer[static_cast<source_type>(i)];
273 };
274
275 if (end - nUnroll > begin) {
276 for (; iter < end - nUnroll; iter += nUnroll) {
277 addQWord(load64(iter));
278 addQWord(load64(iter + ElemsPerQWord));
279 addQWord(load64(iter + 2 * ElemsPerQWord));
280 addQWord(load64(iter + 3 * ElemsPerQWord));
281 this->mNSamples += nUnroll;
282 __builtin_prefetch(iter + 512, 0);
283 }
284 }
285
286 while (iter != end) {
287 ++this->mNSamples;
288 ++this->mContainer[*iter++];
289 }
290 }
291
292 return *this;
293};
294
295template <typename source_T>
296template <typename source_IT>
297auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::addSamplesImpl(source_IT begin, source_IT end, source_type min, source_type max) -> DenseHistogram&
298{
299 if (begin == end) {
300 LOG(warning) << "Passed empty message to " << __func__; // RS this is ok for empty columns
301 } else {
302
303 if (!this->isValidRange(min, max)) {
304 throw HistogramError(fmt::format("Incompatible Frequency table dimensions: Cannot add samples in range [{},{}] to {} int32 histogram.",
305 min, max, []() {if constexpr (std::is_signed_v<source_T>) {return "signed";} else {return "unsigned";} }()));
306 }
307 this->resize(min, max);
308 // add new symbols
309 std::for_each(begin, end, [this](source_type symbol) {
310 ++this->mContainer[symbol];
311 ++this->mNSamples; });
312 }
313
314 return *this;
315}
316
317template <typename source_T>
318template <typename freq_IT>
319auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) == 4>>::addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset) -> DenseHistogram&
320{
321 using namespace internal;
322
323 const auto thisHistogramView = makeHistogramView(this->mContainer);
324 const auto addedHistogramView = trim(HistogramView{begin, end, offset});
325 if (addedHistogramView.empty()) {
326 LOG(warning) << "Passed empty DenseHistogram to " << __func__; // RS this is ok for empty columns
327 } else {
328
329 const difference_type newMin = std::min(thisHistogramView.getMin(), addedHistogramView.getMin());
330 const difference_type newMax = std::max(thisHistogramView.getMax(), addedHistogramView.getMax());
331
332 if (!this->isValidRange(newMin, newMax) ||
333 newMin < static_cast<difference_type>(std::numeric_limits<source_T>::min()) ||
334 newMax > static_cast<difference_type>(std::numeric_limits<source_T>::max())) {
335 throw HistogramError(fmt::format("Incompatible Frequency table dimensions: Cannot add [{},{}] to {} int32 histogram.",
336 addedHistogramView.getMin(),
337 addedHistogramView.getMax(),
338 []() {if constexpr (std::is_signed_v<source_T>) {return "signed";} else {return "unsigned";} }()));
339 };
340
341 if (thisHistogramView.empty()) {
342 this->mContainer = container_type(addedHistogramView.size(), addedHistogramView.getOffset());
343 std::transform(addedHistogramView.begin(), addedHistogramView.end(), this->mContainer.begin(), [this](count_t frequency) {
344 return this->countSamples(frequency);
345 });
346 } else {
347 const difference_type newSize = newMax - newMin + 1;
348 typename container_type::container_type newHistogram(newSize, 0);
349 const auto newHistogramView = makeHistogramView(newHistogram, newMin);
350 auto histogramOverlap = getIntersection(newHistogramView, thisHistogramView);
351 assert(!histogramOverlap.empty());
352 assert(histogramOverlap.size() == thisHistogramView.size());
353 std::copy(thisHistogramView.begin(), thisHistogramView.end(), histogramOverlap.begin());
354
355 histogramOverlap = getIntersection(newHistogramView, addedHistogramView);
356 assert(!histogramOverlap.empty());
357 assert(histogramOverlap.size() == addedHistogramView.size());
358 std::transform(addedHistogramView.begin(), addedHistogramView.end(),
359 histogramOverlap.begin(), histogramOverlap.begin(),
360 [this](const count_t& a, const count_t& b) { return safeadd(this->countSamples(a), b); });
361
362 this->mContainer = container_type{std::move(newHistogram), static_cast<source_type>(newHistogramView.getOffset())};
363 }
364 }
365
366 return *this;
367}
368
369template <typename source_T>
371{
372 using namespace utils;
373
374 auto getMaxSymbol = [this]() {
375 return static_cast<source_type>(this->getOffset() + std::max(0l, static_cast<int32_t>(this->size()) - 1l));
376 };
377
378 min = std::min(min, this->getOffset());
379 max = std::max(max, getMaxSymbol());
380
381 if (min > max) {
382 throw HistogramError(fmt::format("{} failed: min {} > max {} ", __func__, min, max));
383 }
384
385 const size_type newSize = max - min + 1;
386 const source_type oldOffset = this->getOffset();
387 this->mNSamples = 0;
388
389 if (this->mContainer.empty()) {
390 this->mContainer = container_type{newSize, min};
391 return *this;
392 } else {
393 container_type oldHistogram = std::move(this->mContainer);
394 const auto oldHistogramView = makeHistogramView(oldHistogram, oldOffset);
395 this->mContainer = container_type{newSize, min};
396 return this->addFrequencies(oldHistogramView.begin(), oldHistogramView.end(), oldHistogramView.getMin());
397 }
398}
399
400template <typename source_T>
401class DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) <= 2>> : public internal::VectorContainer<source_T, uint32_t>,
403 typename internal::VectorContainer<source_T, uint32_t>::value_type,
404 typename internal::VectorContainer<source_T, uint32_t>::difference_type,
405 DenseHistogram<source_T>>
406{
407 using containerBase_type = internal::VectorContainer<source_T, uint32_t>;
408 using HistogramConcept_type = internal::HistogramConcept<source_T,
412
413 friend containerBase_type;
414 friend HistogramConcept_type;
415
416 public:
417 using source_type = source_T;
418 using value_type = typename containerBase_type::value_type;
419 using container_type = typename containerBase_type::container_type;
420 using size_type = typename containerBase_type::size_type;
421 using difference_type = typename containerBase_type::difference_type;
422 using reference = typename containerBase_type::reference;
423 using const_reference = typename containerBase_type::const_reference;
424 using pointer = typename containerBase_type::pointer;
425 using const_pointer = typename containerBase_type::const_pointer;
426 using const_iterator = typename containerBase_type::const_iterator;
427
428 DenseHistogram() : containerBase_type{MaxSize, std::numeric_limits<source_type>::min()} {};
429
430 template <typename freq_IT>
431 DenseHistogram(freq_IT begin, freq_IT end, difference_type offset) : containerBase_type{MaxSize, std::numeric_limits<source_type>::min()},
432 HistogramConcept_type{begin, end, offset} {};
433
434 using HistogramConcept_type::addSamples;
435
436 template <typename source_IT>
437 inline DenseHistogram& addSamples(source_IT begin, source_IT end, source_type min, source_type max)
438 {
439 return addSamplesImpl(begin, end);
440 };
441
442 template <typename source_IT>
443 DenseHistogram& addSamples(gsl::span<const source_type> span, source_type min, source_type max)
444 {
445 return addSamplesImpl(span);
446 };
447
448 using HistogramConcept_type::addFrequencies;
449
450 protected:
451 template <typename source_IT>
452 DenseHistogram& addSamplesImpl(source_IT begin, source_IT end);
453
454 DenseHistogram& addSamplesImpl(gsl::span<const source_type> samples);
455
456 template <typename freq_IT>
457 DenseHistogram& addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset);
458
459 private:
460 inline static constexpr size_t MaxSize = utils::pow2(utils::toBits<source_type>());
461};
462
463template <typename source_T>
464template <typename source_IT>
465auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) <= 2>>::addSamplesImpl(source_IT begin, source_IT end) -> DenseHistogram&
466{
467 if constexpr (std::is_pointer_v<source_IT>) {
468 return addSamplesImpl({begin, end});
469 } else {
470 std::for_each(begin, end, [this](const source_type& symbol) {
471 ++this->mNSamples;
472 ++this->mContainer[symbol]; });
473 }
474 return *this;
475}
476
477template <typename source_T>
478auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) <= 2>>::addSamplesImpl(gsl::span<const source_type> samples) -> DenseHistogram&
479{
480 using namespace internal;
481 using namespace utils;
482
483 if (samples.empty()) {
484 return *this;
485 }
486
487 const auto begin = samples.data();
488 const auto end = begin + samples.size();
489 constexpr size_t ElemsPerQWord = sizeof(uint64_t) / sizeof(source_type);
490 constexpr size_t nUnroll = 2 * ElemsPerQWord;
491 auto iter = begin;
492
493 if constexpr (sizeof(source_type) == 1) {
494
495 std::array<ShiftableVector<source_type, value_type>, 3> histograms{
496 {{this->mContainer.size(), this->mContainer.getOffset()},
497 {this->mContainer.size(), this->mContainer.getOffset()},
498 {this->mContainer.size(), this->mContainer.getOffset()}}};
499
500 auto addQWord = [&, this](uint64_t in64) {
501 uint64_t i = in64;
502 ++histograms[0][static_cast<source_type>(i)];
503 ++histograms[1][static_cast<source_type>(static_cast<uint16_t>(i) >> 8)];
504 i >>= 16;
505 ++histograms[2][static_cast<source_type>(i)];
506 ++this->mContainer[static_cast<source_type>(static_cast<uint16_t>(i) >> 8)];
507 i = in64 >>= 32;
508 ++histograms[0][static_cast<source_type>(i)];
509 ++histograms[1][static_cast<source_type>(static_cast<uint16_t>(i) >> 8)];
510 i >>= 16;
511 ++histograms[2][static_cast<source_type>(i)];
512 ++this->mContainer[static_cast<source_type>(static_cast<uint16_t>(i) >> 8)];
513 };
514
515 if (end - nUnroll > begin) {
516 for (; iter < end - nUnroll; iter += nUnroll) {
517 addQWord(load64(iter));
518 addQWord(load64(iter + ElemsPerQWord));
519 this->mNSamples += nUnroll;
520 __builtin_prefetch(iter + 512, 0);
521 }
522 }
523
524 while (iter != end) {
525 ++this->mNSamples;
526 ++this->mContainer[*iter++];
527 }
528
529#if defined(RANS_OPENMP)
530#pragma omp unroll full
531#endif
532 for (size_t j = 0; j < 3; ++j) {
533#if defined(RANS_OPENMP) && defined(RANS_SIMD)
534#pragma omp simd
535#endif
536 for (size_t i = 0; i < 256; ++i) {
537 this->mContainer(i) += histograms[j](i);
538 }
539 }
540 } else {
541 container_type histogram{this->mContainer.size(), this->mContainer.getOffset()};
542
543 auto addQWord = [&, this](uint64_t in64) {
544 uint64_t i = in64;
545 ++histogram[static_cast<source_type>(i)];
546 ++this->mContainer[static_cast<source_type>(static_cast<uint32_t>(i) >> 16)];
547 i = in64 >> 32;
548 ++histogram[static_cast<source_type>(i)];
549 ++this->mContainer[static_cast<source_type>(static_cast<uint32_t>(i) >> 16)];
550 };
551
552 if (end - nUnroll > begin) {
553 for (; iter < end - nUnroll; iter += nUnroll) {
554 addQWord(load64(iter));
555 addQWord(load64(iter + ElemsPerQWord));
556 this->mNSamples += nUnroll;
557 __builtin_prefetch(iter + 512, 0);
558 }
559 }
560
561 while (iter != end) {
562 ++this->mNSamples;
563 ++this->mContainer[*iter++];
564 }
565#if defined(RANS_OPENMP) && defined(RANS_SIMD)
566#pragma omp simd
567#endif
568 for (size_t i = 0; i < this->size(); ++i) {
569 this->mContainer.data()[i] += histogram.data()[i];
570 }
571 }
572
573 return *this;
574}
575
576template <typename source_T>
577template <typename freq_IT>
578auto DenseHistogram<source_T, std::enable_if_t<sizeof(source_T) <= 2>>::addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset) -> DenseHistogram&
579{
580 using namespace internal;
581
582 // bounds check
584 addedHistogramView = trim(addedHistogramView);
585
586 if constexpr (std::is_unsigned_v<source_T>) {
587 LOG_IF(warning, addedHistogramView.getMin() < 0) << fmt::format("trying to add frequencies of a signed symbol type to a DenseHistogram of an unsiged type.");
588 }
589 if constexpr (std::is_signed_v<source_T>) {
590 const std::ptrdiff_t sourceTypeMax = std::numeric_limits<source_T>::max();
591 const bool isMinOutOfRange = addedHistogramView.getMin() > sourceTypeMax;
592 const bool isMaxOutOfRange = addedHistogramView.getMax() > sourceTypeMax;
593
594 if (isMaxOutOfRange || isMinOutOfRange) {
595 LOGP(warning, "trying to add frequencies of an unsigned symbol type to a DenseHistogram of a signed type");
596 }
597 }
598
599 const auto thisHistogramView = makeHistogramView(this->mContainer);
600 const bool isInvalidFrequencyRange = utils::toBytes(utils::getRangeBits(addedHistogramView.getMin(), addedHistogramView.getMax())) > sizeof(source_T);
601
602 if (isInvalidFrequencyRange) {
603 throw HistogramError(fmt::format("Incompatible Frequency table dimensions: Cannot add [{},{}] to [{}, {}] ",
604 addedHistogramView.getMin(),
605 addedHistogramView.getMax(),
606 thisHistogramView.getMin(),
607 thisHistogramView.getMax()));
608 }
609
610 auto idx = static_cast<source_type>(addedHistogramView.getOffset()); // We tolerate uint8_t <-> int8_t and uint16_t <-> int16_t conversion.
611 // The resulting overflows are handled correctly by the container via [] operator.
612 for (freq_IT iter = addedHistogramView.begin(); iter != addedHistogramView.end(); ++iter) {
613 auto frequency = *iter;
614 this->mContainer[idx] = safeadd(this->mContainer[idx], this->countSamples(frequency));
615 ++idx;
616 }
617 return *this;
618}
619
620template <typename source_T>
622{
623 return std::count_if(histogram.begin(), histogram.end(), [](typename DenseHistogram<source_T>::const_reference v) { return v != typename DenseHistogram<source_T>::value_type{}; });
624}
625
626} // namespace o2::rans
627
628#endif /* RANS_INTERNAL_CONTAINERS_DENSEHISTOGRAM_H_ */
Abstract container class that defines and implements basic properties shared by histograms and lookup...
int32_t i
Operations that will be performed on a histogram.
Non-owning, lightweight structure for histogram manipulation.
uint32_t j
Definition RawData.h:0
common helper classes and functions
uint32_t source_type
DenseHistogram & addSamplesImpl(source_IT begin, source_IT end)
DenseHistogram & addSamplesImpl(source_IT begin, source_IT end, source_type min, source_type max)
DenseHistogram(freq_IT begin, freq_IT end, difference_type offset)
DenseHistogram & addSamples(source_IT begin, source_IT end, source_type min, source_type max)
DenseHistogram & addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset)
DenseHistogram & addSamples(gsl::span< const source_type > span, source_type min, source_type max)
typename base_type::const_pointer const_pointer
Definition Container.h:97
typename base_type::const_reference const_reference
Definition Container.h:95
typename base_type::value_type value_type
Definition Container.h:90
typename base_type::const_iterator const_iterator
Definition Container.h:98
typename base_type::container_type container_type
Definition Container.h:91
typename base_type::difference_type difference_type
Definition Container.h:93
rans exceptions
GLenum void ** pointer
Definition glcorearb.h:805
GLsizeiptr size
Definition glcorearb.h:659
GLuint GLuint end
Definition glcorearb.h:469
const GLdouble * v
Definition glcorearb.h:832
GLboolean GLboolean GLboolean b
Definition glcorearb.h:1233
GLenum GLint * range
Definition glcorearb.h:1899
GLintptr offset
Definition glcorearb.h:660
GLboolean GLboolean GLboolean GLboolean a
Definition glcorearb.h:1233
auto make_span(const o2::rans::internal::simd::AlignedArray< T, width_V, size_V > &array)
std::pair< source_T, source_T > minmaxImpl(const source_T *begin, const source_T *end)
uint64_t load64(const void *__restrict src)
Definition utils.h:74
std::pair< source_T, source_T > minmax(gsl::span< const source_T > range)
constexpr size_t pow2(size_t n) noexcept
Definition utils.h:165
std::pair< source_T, source_T > minmax(gsl::span< const source_T > range)
auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset) -> DenseHistogram &HistogramView addedHistogramView
const auto thisHistogramView
class DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > > :public internal::VectorContainer< source_T, uint32_t >, internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >{ using containerBase_type=internal::VectorContainer< source_T, uint32_t >;using HistogramConcept_type=internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >;friend containerBase_type;friend HistogramConcept_type;public:using source_type=source_T;using value_type=typename containerBase_type::value_type;using container_type=typename containerBase_type::container_type;using size_type=typename containerBase_type::size_type;using difference_type=typename containerBase_type::difference_type;using reference=typename containerBase_type::reference;using const_reference=typename containerBase_type::const_reference;using pointer=typename containerBase_type::pointer;using const_pointer=typename containerBase_type::const_pointer;using const_iterator=typename containerBase_type::const_iterator;DenseHistogram() :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()} {};template< typename freq_IT > DenseHistogram(freq_IT begin, freq_IT end, difference_type offset) :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()}, HistogramConcept_type{begin, end, offset} {};using HistogramConcept_type::addSamples;template< typename source_IT > inline DenseHistogram &addSamples(source_IT begin, source_IT end, source_type min, source_type max) { return addSamplesImpl(begin, end);};template< typename source_IT > DenseHistogram &addSamples(gsl::span< const source_type > span, source_type min, source_type max) { return addSamplesImpl(span);};using HistogramConcept_type::addFrequencies;protected:template< typename source_IT > DenseHistogram &addSamplesImpl(source_IT begin, source_IT end);DenseHistogram &addSamplesImpl(gsl::span< const source_type > samples);template< typename freq_IT > DenseHistogram &addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset);private:inline static constexpr size_t MaxSize=utils::pow2(utils::toBits< source_type >());};template< typename source_T >template< typename source_IT >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(source_IT begin, source_IT end) -> DenseHistogram &{ if constexpr(std::is_pointer_v< source_IT >) { return addSamplesImpl({begin, end});} else { std::for_each(begin, end, [this](const source_type &symbol) {++this->mNSamples;++this->mContainer[symbol];});} return *this;}template< typename source_T >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(gsl::span< const source_type > samples) -> DenseHistogram &{ using namespace internal;using namespace utils;if(samples.empty()) { return *this;} const auto begin=samples.data();const auto end=begin+samples.size();constexpr size_t ElemsPerQWord=sizeof(uint64_t)/sizeof(source_type);constexpr size_t nUnroll=2 *ElemsPerQWord;auto iter=begin;if constexpr(sizeof(source_type)==1) { std::array< ShiftableVector< source_type, value_type >, 3 > histograms{ {{this-> mContainer this mContainer auto addQWord
class DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > > :public internal::VectorContainer< source_T, uint32_t >, internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >{ using containerBase_type=internal::VectorContainer< source_T, uint32_t >;using HistogramConcept_type=internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >;friend containerBase_type;friend HistogramConcept_type;public:using source_type=source_T;using value_type=typename containerBase_type::value_type;using container_type=typename containerBase_type::container_type;using size_type=typename containerBase_type::size_type;using difference_type=typename containerBase_type::difference_type;using reference=typename containerBase_type::reference;using const_reference=typename containerBase_type::const_reference;using pointer=typename containerBase_type::pointer;using const_pointer=typename containerBase_type::const_pointer;using const_iterator=typename containerBase_type::const_iterator;DenseHistogram() :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()} {};template< typename freq_IT > DenseHistogram(freq_IT begin, freq_IT end, difference_type offset) :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()}, HistogramConcept_type{begin, end, offset} {};using HistogramConcept_type::addSamples;template< typename source_IT > inline DenseHistogram &addSamples(source_IT begin, source_IT end, source_type min, source_type max) { return addSamplesImpl(begin, end);};template< typename source_IT > DenseHistogram &addSamples(gsl::span< const source_type > span, source_type min, source_type max) { return addSamplesImpl(span);};using HistogramConcept_type::addFrequencies;protected:template< typename source_IT > DenseHistogram &addSamplesImpl(source_IT begin, source_IT end);DenseHistogram &addSamplesImpl(gsl::span< const source_type > samples);template< typename freq_IT > DenseHistogram &addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset);private:inline static constexpr size_t MaxSize=utils::pow2(utils::toBits< source_type >());};template< typename source_T >template< typename source_IT >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(source_IT begin, source_IT end) -> DenseHistogram &{ if constexpr(std::is_pointer_v< source_IT >) { return addSamplesImpl({begin, end});} else { std::for_each(begin, end, [this](const source_type &symbol) {++this->mNSamples;++this->mContainer[symbol];});} return *this;}template< typename source_T >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(gsl::span< const source_type > samples) -> DenseHistogram &{ using namespace internal;using namespace utils;if(samples.empty()) { return *this;} const auto begin=samples.data();const auto end=begin+samples.size();constexpr size_t ElemsPerQWord=sizeof(uint64_t)/sizeof(source_type);constexpr size_t nUnroll=2 *ElemsPerQWord;auto iter=begin;if constexpr(sizeof(source_type)==1) { std::array< ShiftableVector< source_type, value_type >, 3 > histograms{ {{this-> mContainer this mContainer getOffset()}
HistogramView< HistA_IT > getIntersection(const HistogramView< HistA_IT > &histA, const HistogramView< HistB_IT > &histB)
class DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > > :public internal::VectorContainer< source_T, uint32_t >, internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >{ using containerBase_type=internal::VectorContainer< source_T, uint32_t >;using HistogramConcept_type=internal::HistogramConcept< source_T, typename internal::VectorContainer< source_T, uint32_t >::value_type, typename internal::VectorContainer< source_T, uint32_t >::difference_type, DenseHistogram< source_T > >;friend containerBase_type;friend HistogramConcept_type;public:using source_type=source_T;using value_type=typename containerBase_type::value_type;using container_type=typename containerBase_type::container_type;using size_type=typename containerBase_type::size_type;using difference_type=typename containerBase_type::difference_type;using reference=typename containerBase_type::reference;using const_reference=typename containerBase_type::const_reference;using pointer=typename containerBase_type::pointer;using const_pointer=typename containerBase_type::const_pointer;using const_iterator=typename containerBase_type::const_iterator;DenseHistogram() :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()} {};template< typename freq_IT > DenseHistogram(freq_IT begin, freq_IT end, difference_type offset) :containerBase_type{MaxSize, std::numeric_limits< source_type >::min()}, HistogramConcept_type{begin, end, offset} {};using HistogramConcept_type::addSamples;template< typename source_IT > inline DenseHistogram &addSamples(source_IT begin, source_IT end, source_type min, source_type max) { return addSamplesImpl(begin, end);};template< typename source_IT > DenseHistogram &addSamples(gsl::span< const source_type > span, source_type min, source_type max) { return addSamplesImpl(span);};using HistogramConcept_type::addFrequencies;protected:template< typename source_IT > DenseHistogram &addSamplesImpl(source_IT begin, source_IT end);DenseHistogram &addSamplesImpl(gsl::span< const source_type > samples);template< typename freq_IT > DenseHistogram &addFrequenciesImpl(freq_IT begin, freq_IT end, difference_type offset);private:inline static constexpr size_t MaxSize=utils::pow2(utils::toBits< source_type >());};template< typename source_T >template< typename source_IT >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(source_IT begin, source_IT end) -> DenseHistogram &{ if constexpr(std::is_pointer_v< source_IT >) { return addSamplesImpl({begin, end});} else { std::for_each(begin, end,[this](const source_type &symbol) {++this->mNSamples;++this->mContainer[symbol];});} return *this;}template< typename source_T >auto DenseHistogram< source_T, std::enable_if_t< sizeof(source_T)<=2 > >::addSamplesImpl(gsl::span< const source_type > samples) -> DenseHistogram &{ using namespace internal;using namespace utils;if(samples.empty()) { return *this;} const auto begin=samples.data();const auto end=begin+samples.size();constexpr size_t ElemsPerQWord=sizeof(uint64_t)/sizeof(source_type);constexpr size_t nUnroll=2 *ElemsPerQWord;auto iter=begin;if constexpr(sizeof(source_type)==1) { std::array< ShiftableVector< source_type, value_type >, 3 > histograms{ {{this-> mContainer size()
auto makeHistogramView(container_T &container, std::ptrdiff_t offset) noexcept -> HistogramView< decltype(std::begin(container))>
return * this
HistogramView< Hist_IT > trim(const HistogramView< Hist_IT > &buffer)
size_t countNUsedAlphabetSymbols(const AdaptiveHistogram< source_T > &histogram)
uint32_t count_t
Definition defaults.h:34
const bool isInvalidFrequencyRange
Enum< T >::Iterator begin(Enum< T >)
Definition Defs.h:173
Defining DataPointCompositeObject explicitly as copiable.
Common utility functions.
wrapper around basic SIMD operations
basic SIMD datatypes and traits
constexpr size_t min
constexpr size_t max
LOG(info)<< "Compressed in "<< sw.CpuTime()<< " s"
pedsdata resize(norbits)
auto getOffset(const map_T &resultsMap) -> typename map_T::key_type