NCBI C++ ToolKit
bmaggregator.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BMAGGREGATOR__H__INCLUDED__
2 #define BMAGGREGATOR__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2022 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmaggregator.h
22  \brief Algorithms for fast aggregation of N bvectors
23 */
24 
25 
26 #ifndef BM__H__INCLUDED__
27 // BitMagic utility headers do not include main "bm.h" declaration
28 // #include "bm.h" or "bm64.h" explicitly
29 # error missing include (bm.h or bm64.h)
30 #endif
31 
32 #include <stdio.h>
33 #include <string.h>
34 
35 
36 #include "bmfunc.h"
37 #include "bmdef.h"
38 
39 #include "bmalgo_impl.h"
40 #include "bmbuffer.h"
41 
42 
43 namespace bm
44 {
45 
46 /*! @name Aggregator traits and control constants
47  @ingroup setalgo
48 */
49 //@{
50 
51 const bool agg_produce_result_bvectors = true;
52 const bool agg_disable_result_bvectors = false;
53 const bool agg_compute_counts = true;
54 const bool agg_disable_counts = false;
55 const bool agg_disable_search_masks = false;
56 
57 /**
58  Aggregation options to control execution
59  Default settings are to support only result bit-vector filters.
60  @ingroup setalgo
61  */
62 template <bool OBvects=bm::agg_produce_result_bvectors,
63  bool OCounts=bm::agg_disable_counts,
64  bool OSearchMasks=bm::agg_disable_search_masks>
66 {
67  /// make result(target) vectors (aggregation search results) (Default: true)
68  /// when false is used - means we want to only collect statistics (counts) for the targets
69  static constexpr bool is_make_results() BMNOEXCEPT { return OBvects; }
70 
71  /// Compute counts for the target vectors, when set to true, population count is computed for
72  /// each result, results itself can be omitted (make_results flag set to false)
73  static constexpr bool is_compute_counts() BMNOEXCEPT { return OCounts; }
74 
75  /// Support for masking operations (Default: false)
76  ///
77  static constexpr bool is_masks() BMNOEXCEPT { return OSearchMasks; }
78 };
79 
80 /**
81  Pre-defined aggregator options to disable both intermediate results and counts
82  @ingroup setalgo
83  */
84 typedef
87 
88 
89 /**
90  Pre-defined aggregator options for counts-only (results dropped) operation
91  @ingroup setalgo
92  */
93 typedef
96 
97 /**
98  Pre-defined aggregator options for results plus counts operation
99  @ingroup setalgo
100  */
101 typedef
104 
105 //@}
106 
107 /**
108  Algorithms for fast aggregation of a group of bit-vectors
109 
110  Algorithms of this class use cache locality optimizations and efficient
111  on cases, wehen we need to apply the same logical operation (aggregate)
112  more than 2x vectors.
113 
114  TARGET = BV1 or BV2 or BV3 or BV4 ...
115 
116  Aggregator supports OR, AND and AND-MINUS (AND-SUB) operations
117 
118  @ingroup setalgo
119 */
120 template<typename BV>
122 {
123 public:
124  typedef BV bvector_type;
125  typedef typename BV::size_type size_type;
126  typedef typename BV::allocator_type allocator_type;
129 
130  typedef typename bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
131  typedef
133  typedef
135  typedef
137 
138 
139  /// Codes for aggregation operations which can be pipelined for efficient execution
140  ///
142  {
144  BM_SHIFT_R_AND = 1
145  };
146 
147  enum class operation_status
148  {
149  op_undefined = 0,
150  op_prepared,
152  op_done
153  };
154 
155  /// Aggregator arg groups
156  struct arg_groups
157  {
158  bv_vector_type arg_bv0; ///< arg group 0
159  bv_vector_type arg_bv1; ///< arg group 1
160  index_vector_type arg_idx0; ///< indexes of vectors for arg group 0
162 
163  /// Reset argument groups to zero
164  void reset()
165  {
166  arg_bv0.resize(0); // TODO: use reset not resize(0)
167  arg_bv1.resize(0);
168  arg_idx0.resize(0);
169  arg_idx1.resize(0);
170  }
171 
172  /** Add bit-vector pointer to its aggregation group
173  \param bv - input bit-vector pointer to attach
174  \param agr_group - input argument group index (0 - default, 1 - fused op)
175 
176  @return current arg group size (0 if vector was not added (empty))
177  */
178  size_t add(const bvector_type* bv, unsigned agr_group);
179  };
180 
181  typedef arg_groups* arg_groups_type_ptr;
182  typedef
184  typedef
186  typedef
188  typedef
190  typedef
192 
193  /**
194  Block cache for pipeline execution
195  @internal
196  */
198  {
199  bv_vector_type bv_inp_vect_; ///< all input vectors from all groups
200  count_vector_type cnt_vect_; ///< usage count for bv_inp (all groups)
201  blockptr_vector_type blk_vect_; ///< cached block ptrs for bv_inp_vect_
202  block_ij_vector_type blk_ij_vect_; ///< current block coords
203  };
204 
205  /**
206  Aggregation options for runtime control
207  */
208  struct run_options
209  {
210  /// Batch size sets number of argument groups processed at a time
211  /// Default: 0 means this parameter will be determined automatically
212  size_t batch_size = 0;
213  };
214 
215  /**
216  Pipeline vector for running a group of aggregation operations on a family of vectors.
217  Pipeline is used to run multiple aggregation combinations (searches) for essencially same
218  set of vectors (different combinations of ANDs and SUBs for example).
219  Pipeline execution improves CPU cache reuse and caches the compressed blocks to re-use it
220  for more efficient execution. Essencially it is a tool to run thousads of runs at once faster.
221  */
222  template<class Opt = bm::agg_run_options<> >
223  class pipeline
224  {
225  public:
226  typedef Opt options_type;
227  public:
228  pipeline() {}
230 
231  /// Set pipeline run options
232  run_options& options() BMNOEXCEPT { return options_; }
233 
234  /// Get pipeline run options
235  const run_options& get_options() const BMNOEXCEPT { return options_; }
236 
237 
238  // ------------------------------------------------------------------
239  /*! @name pipeline argument groups fill-in methods */
240  //@{
241 
242  /** Add new arguments group
243  */
244  arg_groups* add();
245 
246  /**
247  Attach OR (aggregator vector).
248  Pipeline results all will be OR-ed (UNION) into the OR target vector
249  @param bv_or - OR target vector
250  */
252  { bv_or_target_ = bv_or; }
253 
254  /**
255  Set search limit for results. Requires that bit-counting to be enabled in the template parameters.
256  Warning: search limit is approximate (for performance reasons) so it can occasinally find more
257  than requested. It cannot find less.
258  @param limit - search limit (target population count to search for)
259  */
261  { search_count_limit_ = limit; }
262 
263  /** Prepare pipeline for the execution (resize and init internal structures)
264  Once complete, you cannot add() to it.
265  */
266  void complete();
267 
268  /** return true if pipeline is ready for execution (complete) */
270 
271  /**Return size() of pileine */
273 
274  //@}
275 
276  // ------------------------------------------------------------------
277 
278  /** Return argument vector used for pipeline execution */
280  { return arg_vect_; }
281 
282  /** Return results vector used for pipeline execution */
284  { return bv_res_vect_; }
285 
286  /** Return results vector count used for pipeline execution */
288  { return count_res_vect_; }
289 
290 
291  // ------------------------------------------------------------------
292  /*! @name access to internals */
293  //@{
294 
296  { return bcache_.bv_inp_vect_; }
298  { return bcache_.cnt_vect_; }
299 
300  /// Return number of unique vectors in the pipeline (after complete())
302  { return bcache_.bv_inp_vect_.size(); }
303 
304  /// Function looks at the pipeline to apply euristics to suggest optimal run_batch parameter
306  //@}
307 
308  protected:
309  /** @internal */
310  pipeline_bcache& get_bcache() BMNOEXCEPT
311  { return bcache_; }
312  /** Return number of top blocks after complete
313  @internal
314  */
316 
317  private:
318  void complete_arg_group(arg_groups* ag);
320  const bvector_type_const_ptr* bv_src, size_t size);
321 
322  protected:
323  friend class aggregator;
324 
325  pipeline(const pipeline&) = delete;
326  pipeline& operator=(const pipeline&) = delete;
327 
328  protected:
329  run_options options_; ///< execution parameters
330  bool is_complete_ = false; ///< ready to run state flag
331  size_t total_vect_= 0; ///< total number of vector mentions in all groups
332  arg_vector_type arg_vect_; ///< input arg. groups
333 
334  bvect_vector_type bv_res_vect_; ///< results (bit-vector ptrs)
335  bv_count_vector_type count_res_vect_; ///< results (counts)
336  size_type search_count_limit_{bm::id_max}; ///< search limit by count
337 
338  pipeline_bcache bcache_; ///< blocks cache structure
339  unsigned top_blocks_ = 1; ///< top-level structure size, max of all bvectors
340  bvector_type* bv_or_target_ = 0; ///< OR target bit-bector ptr
341  };
342 
343 public:
344 
345  // -----------------------------------------------------------------------
346  /*! @name Construction and setup */
347  //@{
350 
351  /**
352  \brief set on-the-fly bit-block compression
353  By default aggregator does not try to optimize result, but in some cases
354  it can be quite a lot faster than calling bvector<>::optimize() later
355  (because block data sits in CPU cache).
356 
357  \param opt - optimization mode (full compression by default)
358  */
360  typename bvector_type::optmode opt = bvector_type::opt_compress) BMNOEXCEPT
361  { opt_mode_ = opt; }
362 
363  void set_compute_count(bool count_mode) BMNOEXCEPT
364  { compute_count_ = count_mode; count_ = 0; }
365 
366  //@}
367 
368 
369  // -----------------------------------------------------------------------
370 
371  /*! @name Methods to setup argument groups and run operations on groups */
372  //@{
373 
374  /**
375  Attach source bit-vector to a argument group (0 or 1).
376  Arg group 1 used for fused operations like (AND-SUB)
377  \param bv - input bit-vector pointer to attach
378  \param agr_group - input argument group (0 - default, 1 - fused op)
379 
380  @return current arg group size (0 if vector was not added (empty))
381  @sa reset
382  */
383  size_t add(const bvector_type* bv, unsigned agr_group = 0);
384 
385  /**
386  Reset aggregate groups, forget all attached vectors
387  */
388  void reset();
389 
390  /**
391  Aggregate added group of vectors using logical OR
392  Operation does NOT perform an explicit reset of arg group(s)
393 
394  \param bv_target - target vector (input is arg group 0)
395 
396  @sa add, reset
397  */
398  void combine_or(bvector_type& bv_target);
399 
400  /**
401  Aggregate added group of vectors using logical AND
402  Operation does NOT perform an explicit reset of arg group(s)
403 
404  \param bv_target - target vector (input is arg group 0)
405 
406  @sa add, reset
407  */
408  void combine_and(bvector_type& bv_target);
409 
410  /**
411  Aggregate added group of vectors using fused logical AND-SUB
412  Operation does NOT perform an explicit reset of arg group(s)
413 
414  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
415 
416  \return true if anything was found
417 
418  @sa add, reset
419  */
420  bool combine_and_sub(bvector_type& bv_target);
421 
422  /**
423  Run AND-SUB: AND (groups1) AND NOT ( OR(group0)) for a pipeline
424  @param pipe - pipeline to run (should be prepared, filled and complete
425  */
426  template<class TPipe>
427  void combine_and_sub(TPipe& pipe);
428 
429 
430 
431  /**
432  Aggregate added group of vectors using fused logical AND-SUB
433  Operation does NOT perform an explicit reset of arg group(s)
434  Operation can terminate early if anything was found.
435 
436  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
437  \param any - if true, search result will terminate of first found result
438 
439  \return true if anything was found
440 
441  @sa add, reset, find_first_and_sub
442  */
443  bool combine_and_sub(bvector_type& bv_target, bool any);
444 
445  /**
446  Aggregate added group of vectors using fused logical AND-SUB.
447  search traget is back_inserter
448  */
449  template<typename BII>
450  bool combine_and_sub_bi(BII bi);
451 
452  /**
453  Aggregate added group of vectors using fused logical AND-SUB,
454  find the first match
455 
456  \param idx - [out] index of the first occurence
457  \return true if anything was found
458  @sa combine_and_sub
459  */
461 
462 
463  /**
464  Aggregate added group of vectors using SHIFT-RIGHT and logical AND
465  Operation does NOT perform an explicit reset of arg group(s)
466 
467  \param bv_target - target vector (input is arg group 0)
468 
469  @return bool if anything was found
470 
471  @sa add, reset
472  */
474 
475  /**
476  Set search hint for the range, where results needs to be searched
477  (experimental for internal use).
478  @return true if range is one-block bound
479  @internal
480  */
482 
483  /**
484  Reset range hint to false
485  */
487 
488  size_type count() const { return count_; }
489 
490  //@}
491 
492  // -----------------------------------------------------------------------
493 
494  /*! @name Logical operations (C-style interface) */
495  //@{
496 
497  /**
498  Aggregate group of vectors using logical OR
499  \param bv_target - target vector
500  \param bv_src - array of pointers on bit-vector aggregate arguments
501  \param src_size - size of bv_src (how many vectors to aggregate)
502  */
503  void combine_or(bvector_type& bv_target,
504  const bvector_type_const_ptr* bv_src, size_t src_size);
505 
506  /**
507  Aggregate group of vectors using logical AND
508  \param bv_target - target vector
509  \param bv_src - array of pointers on bit-vector aggregate arguments
510  \param src_size - size of bv_src (how many vectors to aggregate)
511  */
512  void combine_and(bvector_type& bv_target,
513  const bvector_type_const_ptr* bv_src, size_t src_size);
514 
515  /**
516  Fusion aggregate group of vectors using logical AND MINUS another set
517 
518  \param bv_target - target vector
519  \param bv_src_and - array of pointers on bit-vectors for AND
520  \param src_and_size - size of AND group
521  \param bv_src_sub - array of pointers on bit-vectors for SUBstract
522  \param src_sub_size - size of SUB group
523  \param any - flag if caller needs any results asap (incomplete results)
524 
525  \return true when found
526  */
527  bool combine_and_sub(bvector_type& bv_target,
528  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
529  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size,
530  bool any);
531 
532  template<typename BII>
533  bool combine_and_sub(BII bi,
534  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
535  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size);
536 
537 
539  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
540  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size);
541 
542  /**
543  Fusion aggregate group of vectors using SHIFT right with AND
544 
545  \param bv_target - target vector
546  \param bv_src_and - array of pointers on bit-vectors for AND masking
547  \param src_and_size - size of AND group
548  \param any - flag if caller needs any results asap (incomplete results)
549 
550  \return true when found
551  */
553  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
554  bool any);
555 
556 
557  //@}
558 
559  // -----------------------------------------------------------------------
560 
561  /*! @name Horizontal Logical operations used for tests (C-style interface) */
562  //@{
563 
564  /**
565  Horizontal OR aggregation (potentially slower) method.
566  \param bv_target - target vector
567  \param bv_src - array of pointers on bit-vector aggregate arguments
568  \param src_size - size of bv_src (how many vectors to aggregate)
569  */
571  const bvector_type_const_ptr* bv_src,
572  size_t src_size);
573  /**
574  Horizontal AND aggregation (potentially slower) method.
575  \param bv_target - target vector
576  \param bv_src - array of pointers on bit-vector aggregate arguments
577  \param src_size - size of bv_src (how many vectors to aggregate)
578  */
580  const bvector_type_const_ptr* bv_src,
581  size_t src_size);
582 
583  /**
584  Horizontal AND-SUB aggregation (potentially slower) method.
585  \param bv_target - target vector
586  \param bv_src_and - array of pointers on bit-vector to AND aggregate
587  \param src_and_size - size of bv_src_and
588  \param bv_src_sub - array of pointers on bit-vector to SUB aggregate
589  \param src_sub_size - size of bv_src_sub
590  */
592  const bvector_type_const_ptr* bv_src_and,
593  size_t src_and_size,
594  const bvector_type_const_ptr* bv_src_sub,
595  size_t src_sub_size);
596 
597  //@}
598 
599 
600  // -----------------------------------------------------------------------
601 
602  /*! @name Pipeline operations */
603  //@{
604 
605  /** Get current operation code */
607 
608  /** Set operation code for the aggregator */
609  void set_operation(int op_code) BMNOEXCEPT { operation_ = op_code; }
610 
611  /**
612  Prepare operation, create internal resources, analyse dependencies.
613  Prerequisites are: that operation is set and all argument vectors are added
614  */
615  void stage(bm::word_t* temp_block);
616 
617  /**
618  Run a step of current arrgegation operation
619  */
620  operation_status run_step(unsigned i, unsigned j);
621 
623 
625 
627 
628  //@}
629 
630  // -----------------------------------------------------------------------
631 
632  /*! @name Execition metrics and telemetry */
633  //@{
635  //@}
636 
637 protected:
638  typedef typename bvector_type::blocks_manager_type blocks_manager_type;
639  typedef typename BV::block_idx_type block_idx_type;
640  typedef
642  typedef
644  typedef
646 
647 
648  void reset_vars();
649 
650 
651  void combine_or(unsigned i, unsigned j,
652  bvector_type& bv_target,
653  const bvector_type_const_ptr* bv_src, size_t src_size);
654 
655  void combine_and(unsigned i, unsigned j,
656  bvector_type& bv_target,
657  const bvector_type_const_ptr* bv_src, size_t src_size);
658 
659  digest_type combine_and_sub(unsigned i, unsigned j,
660  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
661  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size,
662  int* is_result_full,
663  bool find_all);
664 
666  const bvector_type_const_ptr* bv_src,
667  size_t src_size);
668 
669  bool combine_shift_right_and(unsigned i, unsigned j,
670  bvector_type& bv_target,
671  const bvector_type_const_ptr* bv_src,
672  size_t src_size);
673 
674  static
675  unsigned resize_target(bvector_type& bv_target,
676  const bvector_type_const_ptr* bv_src,
677  size_t src_size,
678  bool init_clear = true);
679 
680  static
681  unsigned max_top_blocks(const bvector_type_const_ptr* bv_src,
682  size_t src_size) BMNOEXCEPT;
683 
684 
685 
686  /// Temporary operations vectors
687  struct arena
688  {
689  block_ptr_vector_type v_arg_tmp_blk; ///< source blocks list
690  block_ptr_vector_type v_arg_or_blk; ///< source blocks list (OR)
691  gap_block_ptr_vector_type v_arg_or_blk_gap; ///< source GAP blocks list (OR)
692  block_ptr_vector_type v_arg_and_blk; ///< source blocks list (AND)
693  gap_block_ptr_vector_type v_arg_and_blk_gap; ///< source GAP blocks list (AND)
694  uchar_vector_type carry_overs; ///< shift carry over flags
695 
696 
698  {
699  reset_or_blocks();
701  carry_overs.reset();
702  }
704  {
707  }
709  {
712  }
713 
714  };
715 
716 
717  bm::word_t* sort_input_blocks_or(//const size_t* src_idx,
718  const bvector_type_const_ptr* bv_src,
719  size_t src_size,
720  unsigned i, unsigned j);
721 
722  bm::word_t* sort_input_blocks_and(//const size_t* src_idx,
723  const bvector_type_const_ptr* bv_src,
724  size_t src_size,
725  unsigned i, unsigned j);
727  const size_t* src_idx,
728  size_t k,
729  unsigned i, unsigned j);
730 
731 
733  unsigned i, unsigned j, const arena& ar);
734 
735  void process_gap_blocks_or(const arena& ar/*size_t block_count*/);
736 
738  digest_type digest,
739  bool find_all);
740 
741  digest_type process_gap_blocks_and(const arena& ar, /*size_t block_count,*/ digest_type digest);
742 
743  bool test_gap_blocks_and(size_t block_count, unsigned bit_idx);
744  bool test_gap_blocks_sub(size_t block_count, unsigned bit_idx);
745 
746  digest_type process_bit_blocks_sub(const arena& ar, /*size_t block_count,*/ digest_type digest);
747 
748  digest_type process_gap_blocks_sub(const arena& ar,/*size_t block_count,*/ digest_type digest);
749 
750  static
751  unsigned find_effective_sub_block_size(unsigned i,
752  const bvector_type_const_ptr* bv_src,
753  size_t src_size,
754  bool top_null_as_zero) BMNOEXCEPT;
755 
756  static
757  unsigned find_effective_sub_block_size(unsigned i,
758  const bvector_type_const_ptr* bv_src1,
759  size_t src_size1,
760  const bvector_type_const_ptr* bv_src2,
761  size_t src_size2) BMNOEXCEPT;
762 
763  static
764  bool any_carry_overs(const unsigned char* carry_overs,
765  size_t co_size) BMNOEXCEPT;
766 
767  /**
768  @return carry over
769  */
770  static
772  const bm::word_t* BMRESTRICT arg_blk,
773  digest_type& BMRESTRICT digest,
774  unsigned carry_over) BMNOEXCEPT;
775 
776  static
778  unsigned k, unsigned i, unsigned j) BMNOEXCEPT;
779 
781 
782  // ---------------------------------------------------------
783 
784  static arena* construct_arena()
785  {
786  void* p = bm::aligned_new_malloc(sizeof(arena));
787  return new(p) arena();
788  }
789  static void free_arena(arena* ar) BMNOEXCEPT
790  {
791  if (!ar) return;
792  ar->~arena();
793  bm::aligned_free(ar);
794  }
795 
796  static arg_groups* construct_arg_group()
797  {
798  void* p = bm::aligned_new_malloc(sizeof(arg_groups));
799  return new(p) arg_groups();
800  }
801 
802  static void free_arg_group(arg_groups* arg)
803  {
804  if (!arg) return;
805  arg->~arg_groups();
806  bm::aligned_free(arg);
807  }
808 
809  // ---------------------------------------------------------
810 
811 private:
812  /// Alllocated blocka of scratch memory
813  struct tb_arena
814  {
816  BM_DECLARE_TEMP_BLOCK(tb_opt) ///< temp block for results optimization
817  };
818 
819 
821  aggregator& operator=(const aggregator&) = delete;
822 
823 private:
824  arg_groups ag_; ///< aggregator argument groups
825  tb_arena* tb_ar_; ///< data arena ptr (heap allocated)
826  arena* ar_; ///< data arena ptr
827  allocator_pool_type pool_; ///< pool for operations with cyclic mem.use
828 
829  bm::word_t* temp_blk_= 0; ///< external temp block ptr
830  int operation_ = 0; ///< operation code (default: not defined)
832  bvector_type* bv_target_ = 0; ///< target bit-vector
833  unsigned top_block_size_ = 0; ///< operation top block (i) size
834  pipeline_bcache* bcache_ptr_ = 0; /// pipeline blocks cache ptr
835 
836  // search range setting (hint) [from, to]
837  bool range_set_ = false; ///< range flag
838  size_type range_from_ = bm::id_max; ///< search from
839  size_type range_to_ = bm::id_max; ///< search to
840  bm::gap_word_t range_gap_blk_[5] {0,}; ///< temp GAP range block
841 
842  // single bit reduction flag
843  bool is_single_bit_ = false; ///< single bit flag
844  unsigned single_bit_idx_ = 0;
845 
846 
847 
848  typename bvector_type::optmode opt_mode_; ///< perform search result optimization
849  bool compute_count_; ///< compute search result count
850  size_type count_; ///< search result count
851  //
852  // execution telemetry and metrics
854 };
855 
856 
857 
858 
859 // ------------------------------------------------------------------------
860 //
861 // ------------------------------------------------------------------------
862 
863 /**
864  Experimental method ro run multiple aggregators in sync
865 
866  Pipeleine algorithm walts the sequence of iterators (pointers on aggregators)
867  and run them all via aggregator<>::run_step() method
868 
869  @param first - iterator (pointer on aggregator)
870  @param last - iterator (pointer on aggregator)
871  @ingroup setalgo
872 */
873 template<typename Agg, typename It>
875 {
876  bm::word_t* tb = (*first)->get_temp_block();
877 
878  int pipeline_size = 0;
879  for (It it = first; it != last; ++it, ++pipeline_size)
880  {
881  Agg& agg = *(*it);
882  agg.stage(tb);
883  }
884  for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
885  {
886  unsigned j = 0;
887  do
888  {
889  // run all aggregators for the [i,j] coordinate
890  unsigned w = 0;
891  for (It it = first; it != last; ++it, ++w)
892  {
893  Agg& agg = *(*it);
894  auto op_st = agg.get_operation_status();
895  if (op_st != Agg::operation_status::op_done)
896  {
897  op_st = agg.run_step(i, j);
898  pipeline_size -= (op_st == Agg::operation_status::op_done);
899  }
900  } // for it
901  if (pipeline_size <= 0)
902  return;
903 
904  } while (++j < bm::set_sub_array_size);
905 
906  } // for i
907 }
908 
909 
910 // ------------------------------------------------------------------------
911 //
912 // ------------------------------------------------------------------------
913 
914 
915 template<typename BV>
917 : opt_mode_(bvector_type::opt_none),
919  count_(0)
920 {
922  ar_ = construct_arena();
923 }
924 
925 // ------------------------------------------------------------------------
926 
927 template<typename BV>
929 {
930  BM_ASSERT(ar_ && tb_ar_);
931  bm::aligned_free(tb_ar_);
932 
933  free_arena(ar_);
934 
935  delete bv_target_;
936 }
937 
938 // ------------------------------------------------------------------------
939 
940 template<typename BV>
942 {
943  reset_vars();
944  reset_range_hint();
945 }
946 
947 // ------------------------------------------------------------------------
948 
949 template<typename BV>
951 {
952  ag_.reset();
953  ar_->reset_all_blocks();
954  operation_ = top_block_size_ = 0;
955  operation_status_ = operation_status::op_undefined;
956  count_ = 0; bcache_ptr_ = 0; gap_cache_cnt_ = 0;
957 }
958 
959 // ------------------------------------------------------------------------
960 
961 template<typename BV>
963 {
964  range_set_ = false;
965  range_from_ = range_to_ = bm::id_max;
966  range_gap_blk_[0] = 0;
967  is_single_bit_ = false;
968 }
969 
970 
971 // ------------------------------------------------------------------------
972 
973 template<typename BV>
975 {
976  range_from_ = from; range_to_ = to;
977  range_set_ = true;
978  typename bvector_type::block_idx_type
979  nb_from {from >> bm::set_block_shift}, nb_to {to >> bm::set_block_shift};
980  if (nb_from == nb_to)
981  {
982  gap_init_range_block<gap_word_t>(
983  range_gap_blk_,
984  (gap_word_t)unsigned(from & bm::set_block_mask),
985  (gap_word_t)unsigned(to & bm::set_block_mask),
986  (gap_word_t)1);
987  return true; // one block hit
988  }
989  else
990  {
991  range_gap_blk_[0] = 0;
992  }
993  return false; // range crosses the blocks boundaries
994 }
995 
996 // ------------------------------------------------------------------------
997 
998 template<typename BV>
1001 {
1002  if (!bv_target_)
1003  {
1004  bv_target_ = new bvector_type(); //TODO: get rid of "new"
1005  bv_target_->init();
1006  }
1007  return bv_target_;
1008 }
1009 
1010 // ------------------------------------------------------------------------
1011 
1012 template<typename BV>
1013 size_t aggregator<BV>::add(const bvector_type* bv, unsigned agr_group)
1014 {
1015  return ag_.add(bv, agr_group);
1016 }
1017 
1018 // ------------------------------------------------------------------------
1019 
1020 template<typename BV>
1022 {
1023  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1024  combine_or(bv_target, ag_.arg_bv0.data(), ag_.arg_bv0.size());
1025 }
1026 
1027 // ------------------------------------------------------------------------
1028 
1029 template<typename BV>
1031 {
1032  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1033  //combine_and(bv_target, ag_.arg_bv0.data(), ag_.arg_bv0.size());
1034  // implemented ad AND-SUB (with an empty MINUS set)
1035  combine_and_sub(bv_target,
1036  ag_.arg_bv0.data(), ag_.arg_bv0.size(),
1037  0, 0,
1038  false);
1039 }
1040 
1041 // ------------------------------------------------------------------------
1042 
1043 template<typename BV>
1045 {
1046  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1047  return combine_and_sub(bv_target,
1048  ag_.arg_bv0.data(), ag_.arg_bv0.size(),
1049  ag_.arg_bv1.data(), ag_.arg_bv1.size(),
1050  false);
1051 }
1052 
1053 // ------------------------------------------------------------------------
1054 
1055 template<typename BV>
1057 {
1058  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1059  return combine_and_sub(bv_target,
1060  ag_.arg_bv0.data(), ag_.arg_bv0.size(),
1061  ag_.arg_bv1.data(), ag_.arg_bv1.size(),
1062  any);
1063 }
1064 
1065 // ------------------------------------------------------------------------
1066 
1067 template<typename BV> template<typename BII>
1069 {
1070  return combine_and_sub(bi,
1071  ag_.arg_bv0.data(), ag_.arg_bv0.size(),
1072  ag_.arg_bv1.data(), ag_.arg_bv1.size());
1073 }
1074 
1075 
1076 // ------------------------------------------------------------------------
1077 
1078 template<typename BV>
1080 {
1081  return find_first_and_sub(idx,
1082  ag_.arg_bv0.data(), ag_.arg_bv0.size(), //arg_group0_size,
1083  ag_.arg_bv1.data(), ag_.arg_bv1.size());//arg_group1_size);
1084 }
1085 
1086 // ------------------------------------------------------------------------
1087 
1088 template<typename BV>
1090 {
1091  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1092  count_ = 0;
1093  ar_->reset_all_blocks();
1094  combine_shift_right_and(bv_target, ag_.arg_bv0.data(), ag_.arg_bv0.size(),//arg_group0_size,
1095  false);
1096 }
1097 
1098 // ------------------------------------------------------------------------
1099 
1100 template<typename BV>
1102  const bvector_type_const_ptr* bv_src, size_t src_size)
1103 {
1104  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1105  if (!src_size)
1106  {
1107  bv_target.clear();
1108  return;
1109  }
1110  ag_.reset();
1111  ar_->reset_or_blocks();
1112  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
1113  for (unsigned i = 0; i < top_blocks; ++i)
1114  {
1115  unsigned set_array_max =
1116  find_effective_sub_block_size(i, bv_src, src_size, false);
1117  for (unsigned j = 0; j < set_array_max; ++j)
1118  {
1119  combine_or(i, j, bv_target, bv_src, src_size);
1120  } // for j
1121  } // for i
1122 }
1123 
1124 // ------------------------------------------------------------------------
1125 
1126 template<typename BV>
1128  const bvector_type_const_ptr* bv_src,
1129  size_t src_size)
1130 {
1131  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1132  if (src_size == 1)
1133  {
1134  const bvector_type* bv = bv_src[0];
1135  bv_target = *bv;
1136  return;
1137  }
1138  if (!src_size)
1139  {
1140  bv_target.clear();
1141  return;
1142  }
1143  ag_.reset();
1144  ar_->reset_and_blocks();
1145  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
1146  for (unsigned i = 0; i < top_blocks; ++i)
1147  {
1148  // TODO: find range, not just size
1149  unsigned set_array_max =
1150  find_effective_sub_block_size(i, bv_src, src_size, true);
1151  for (unsigned j = 0; j < set_array_max; ++j)
1152  {
1153  // TODO: use block_managers not bvectors to avoid extra indirect
1154  combine_and(i, j, bv_target, bv_src, src_size);
1155  } // for j
1156  } // for i
1157 }
1158 
1159 // ------------------------------------------------------------------------
1160 
1161 template<typename BV>
1163  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
1164  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size,
1165  bool any)
1166 {
1167  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
1168  bool global_found = false;
1169 
1170  if (!bv_src_and || !src_and_size)
1171  {
1172  bv_target.clear();
1173  return false;
1174  }
1175 
1176  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1177 
1178  unsigned top_blocks = resize_target(bv_target, bv_src_and, src_and_size);
1179  unsigned top_blocks2 = resize_target(bv_target, bv_src_sub, src_sub_size, false);
1180 
1181  if (top_blocks2 > top_blocks)
1182  top_blocks = top_blocks2;
1183 
1184  for (unsigned i = 0; i < top_blocks; ++i)
1185  {
1186  const unsigned set_array_max =
1187  find_effective_sub_block_size(i, bv_src_and, src_and_size,
1188  bv_src_sub, src_sub_size);
1189  for (unsigned j = 0; j < set_array_max; ++j)
1190  {
1191  int is_res_full;
1192  digest_type digest = combine_and_sub(i, j,
1193  /*0,*/ bv_src_and, src_and_size,
1194  /*0,*/ bv_src_sub, src_sub_size,
1195  &is_res_full, !any);
1196  if (is_res_full)
1197  {
1198  bman_target.check_alloc_top_subblock(i);
1199  bman_target.set_block_ptr(i, j, (bm::word_t*)FULL_BLOCK_FAKE_ADDR);
1200  if (j == bm::set_sub_array_size-1)
1201  bman_target.validate_top_full(i);
1202  if (any)
1203  return any;
1204  }
1205  else
1206  {
1207  bool found = digest;
1208  if (found)
1209  {
1210  bman_target.opt_copy_bit_block(i, j, tb_ar_->tb1,
1211  bvector_type::opt_compress, tb_ar_->tb_opt);
1212  if (any)
1213  return found;
1214  }
1215  global_found |= found;
1216  }
1217  } // for j
1218  } // for i
1219  return global_found;
1220 }
1221 
1222 // ------------------------------------------------------------------------
1223 
1224 template<typename BV> template<typename BII>
1226  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
1227  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size)
1228 {
1229  bool global_found = false;
1230 
1231  if (!bv_src_and || !src_and_size)
1232  return false;
1233 
1234  unsigned top_blocks = 0;
1235 
1236  // pre-scan to calculate top size
1237  for (unsigned i = 0; i < src_and_size; ++i)
1238  {
1239  const bvector_type* bv = bv_src_and[i];
1240  BM_ASSERT(bv);
1241  unsigned arg_top_blocks = bv->get_blocks_manager().top_block_size();
1242  if (arg_top_blocks > top_blocks)
1243  top_blocks = arg_top_blocks;
1244  } // for i
1245  for (unsigned i = 0; i < src_sub_size; ++i)
1246  {
1247  const bvector_type* bv = bv_src_sub[i];
1248  BM_ASSERT(bv);
1249  unsigned arg_top_blocks = bv->get_blocks_manager().top_block_size();
1250  if (arg_top_blocks > top_blocks)
1251  top_blocks = arg_top_blocks;
1252  } // for i
1253 
1255  for (unsigned i = 0; i < top_blocks; ++i)
1256  {
1257  const unsigned set_array_max =
1258  find_effective_sub_block_size(i, bv_src_and, src_and_size,
1259  bv_src_sub, src_sub_size);
1260  for (unsigned j = 0; j < set_array_max; ++j)
1261  {
1262  int is_res_full;
1263  digest_type digest = combine_and_sub(i, j,
1264  /*0,*/ bv_src_and, src_and_size,
1265  /*0,*/ bv_src_sub, src_sub_size,
1266  &is_res_full, true);
1268  size_type base_idx = (r+j)*bm::bits_in_block;
1269  if (is_res_full)
1270  {
1271  for (size_type k = 0; k < 65536; ++k)
1272  *bi = base_idx + k;
1273  }
1274  else
1275  {
1276  bool found = digest;
1277  global_found |= found;
1278  if (found)
1279  bm::for_each_bit_blk(tb_ar_->tb1, base_idx, bit_functor);
1280  }
1281  } // for j
1282  } // for i
1283  return global_found;
1284 
1285 }
1286 
1287 
1288 
1289 // ------------------------------------------------------------------------
1290 
1291 template<typename BV> template<class TPipe>
1293 {
1294  BM_ASSERT(pipe.is_complete());
1295 
1296  const arg_vector_type& pipe_args = pipe.get_args_vector();
1297  size_t pipe_size = pipe_args.size();
1298  if (!pipe_size)
1299  return;
1300 
1301  reset_vars();
1302 
1303  bcache_ptr_ = &pipe.get_bcache(); // setup common cache block
1304 
1305  unsigned top_blocks = pipe.get_top_blocks();
1306  BM_ASSERT(top_blocks);
1307 
1308  if (pipe.bv_or_target_)
1309  pipe.bv_or_target_->get_blocks_manager().reserve_top_blocks(top_blocks);
1310 
1311  unsigned i_from(0), j_from(0), i_to(0), j_to(0);
1312  if (range_set_)
1313  {
1314  typename bvector_type::block_idx_type nb;
1315  nb = (range_from_ >> bm::set_block_shift);
1316  bm::get_block_coord(nb, i_from, j_from);
1317  nb = (range_to_ >> bm::set_block_shift);
1318  bm::get_block_coord(nb, i_to, j_to);
1319  }
1320 
1321 
1322  size_t batch_size = pipe.get_options().batch_size;
1323  if (!batch_size)
1324  batch_size = pipe.compute_run_batch();
1325 
1326  for (size_t batch_from(0), batch_to(0); batch_from < pipe_size;
1327  batch_from = batch_to)
1328  {
1329  batch_to = batch_from + batch_size;
1330  if (batch_to > pipe_size)
1331  batch_to = pipe_size;
1332  if (!batch_size)
1333  batch_size = 1;
1334  for (unsigned i = i_from; i < top_blocks; ++i)
1335  {
1336  unsigned j(0), sub_size(bm::set_sub_array_size);
1337  if constexpr(TPipe::options_type::is_masks())
1338  {
1339  if (range_set_)
1340  {
1341  if (i == i_from)
1342  j = j_from;
1343  if (i == i_to)
1344  sub_size = j_to+1;
1345  }
1346  }
1347 
1348  for (; j < sub_size; ++j)
1349  {
1350  size_t p = batch_from;
1351  for (; p < batch_to; ++p)
1352  {
1353  const arg_groups* ag = pipe_args[p];
1354  size_t src_and_size = ag->arg_bv0.size();
1355  if (!src_and_size)
1356  continue;
1357 
1358  const bvector_type_const_ptr* bv_src_and = ag->arg_bv0.data();
1359  const bvector_type_const_ptr* bv_src_sub = ag->arg_bv1.data();
1360  size_t src_sub_size = ag->arg_bv1.size();
1361 
1362  if constexpr (TPipe::options_type::is_compute_counts())
1363  {
1364  // if search limit reached
1365  if (pipe.count_res_vect_[p] >= pipe.search_count_limit_)
1366  continue;
1367  }
1368 
1369  int is_res_full;
1370  digest_type digest = combine_and_sub(i, j,
1371  bv_src_and, src_and_size,
1372  bv_src_sub, src_sub_size,
1373  &is_res_full,
1374  true // find all
1375  );
1376  if (digest || is_res_full)
1377  {
1378  if (pipe.bv_or_target_)
1379  {
1380  blocks_manager_type& bman =
1381  pipe.bv_or_target_->get_blocks_manager();
1382  const bm::word_t* arg_blk =
1383  (is_res_full) ? (bm::word_t*)FULL_BLOCK_FAKE_ADDR
1384  : tb_ar_->tb1;
1385  bman.check_alloc_top_subblock(i);
1386  bm::word_t* blk = bman.get_block_ptr(i, j);
1387  pipe.bv_or_target_->combine_operation_block_or(
1388  i, j, blk, arg_blk);
1389  }
1390  if constexpr (!TPipe::options_type::is_make_results()) // drop results
1391  {
1392  if constexpr (TPipe::options_type::is_compute_counts())
1393  {
1394  if (is_res_full)
1395  pipe.count_res_vect_[p]+=bm::gap_max_bits;
1396  else
1397  pipe.count_res_vect_[p]+=
1398  bm::bit_block_count(tb_ar_->tb1, digest);
1399  }
1400  }
1401  else // results requested
1402  {
1403  bvect_vector_type& bv_targets_vect =
1404  pipe.get_bv_res_vector();
1405  bvector_type* bv_target = bv_targets_vect[p];
1406  if (!bv_target)
1407  {
1408  BM_ASSERT(!bv_targets_vect[p]);
1409  bv_target = new bvector_type(bm::BM_GAP);
1410  bv_targets_vect[p] = bv_target;
1411  typename bvector_type::blocks_manager_type& bman =
1412  bv_target->get_blocks_manager();
1413 
1414  bman.reserve_top_blocks(top_blocks);
1415  }
1416  blocks_manager_type& bman =
1417  bv_target->get_blocks_manager();
1418  if (is_res_full)
1419  {
1420  bman.check_alloc_top_subblock(i);
1421  bman.set_block_ptr(i, j,
1423  if (j == bm::set_sub_array_size-1)
1424  bman.validate_top_full(i);
1425  if constexpr (TPipe::options_type::is_compute_counts())
1426  pipe.count_res_vect_[p] += bm::gap_max_bits;
1427  }
1428  else
1429  {
1430  if constexpr (TPipe::options_type::is_compute_counts())
1431  pipe.count_res_vect_[p] +=
1432  bm::bit_block_count(tb_ar_->tb1, digest);
1433  bman.opt_copy_bit_block(i, j, tb_ar_->tb1,
1434  bvector_type::opt_compress, tb_ar_->tb_opt);
1435  }
1436  }
1437  } // if
1438  } // for p
1439  // optimize OR target to save memory
1440  if (pipe.bv_or_target_ && p == pipe_size) // last batch is done
1441  {
1442  blocks_manager_type& bman =
1443  pipe.bv_or_target_->get_blocks_manager();
1444  if (bm::word_t* blk = bman.get_block_ptr(i, j))
1445  bman.optimize_block(i, j, blk,
1446  tb_ar_->tb_opt, bvector_type::opt_compress, 0);
1447  }
1448  } // for j
1449  } // for i
1450  } // for batch
1451 
1452  bcache_ptr_ = 0;
1453 }
1454 
1455 // ------------------------------------------------------------------------
1456 
1457 template<typename BV>
1459  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
1460  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size)
1461 {
1462  unsigned top_blocks = max_top_blocks(bv_src_and, src_and_size);
1463  unsigned top_blocks2 = max_top_blocks(bv_src_sub, src_sub_size);
1464 
1465  if (top_blocks2 > top_blocks)
1466  top_blocks = top_blocks2;
1467 
1468  // compute range blocks coordinates
1469  //
1470  block_idx_type nblock_from = (range_from_ >> bm::set_block_shift);
1471  block_idx_type nblock_to = (range_to_ >> bm::set_block_shift);
1472  unsigned top_from = unsigned(nblock_from >> bm::set_array_shift);
1473  unsigned top_to = unsigned(nblock_to >> bm::set_array_shift);
1474 
1475  if (range_set_)
1476  {
1477  if (nblock_from == nblock_to) // one block search
1478  {
1479  int is_res_full;
1480  unsigned i = top_from;
1481  unsigned j = unsigned(nblock_from & bm::set_array_mask);
1482  digest_type digest = combine_and_sub(i, j,
1483  bv_src_and, src_and_size,
1484  bv_src_sub, src_sub_size,
1485  &is_res_full, false // first
1486  );
1487  // is_res_full is not needed here, since it is just 1 block
1488  if (digest)
1489  {
1490  unsigned block_bit_idx = 0;
1491  bool found = bm::bit_find_first(tb_ar_->tb1, &block_bit_idx, digest);
1492  BM_ASSERT(found);
1493  idx = bm::block_to_global_index(i, j, block_bit_idx);
1494  return found;
1495  }
1496  return false;
1497  }
1498 
1499  if (top_to < top_blocks)
1500  top_blocks = top_to+1;
1501  }
1502  else
1503  {
1504  top_from = 0;
1505  }
1506 
1507  for (unsigned i = top_from; i < top_blocks; ++i)
1508  {
1509  unsigned set_array_max = bm::set_sub_array_size;
1510  unsigned j = 0;
1511  if (range_set_)
1512  {
1513  if (i == top_from)
1514  j = nblock_from & bm::set_array_mask;
1515  if (i == top_to)
1516  set_array_max = 1 + unsigned(nblock_to & bm::set_array_mask);
1517  }
1518  else
1519  {
1520  set_array_max = find_effective_sub_block_size(i, bv_src_and, src_and_size, true);
1521  if (!set_array_max)
1522  continue;
1523  if (src_sub_size)
1524  {
1525  unsigned set_array_max2 =
1526  find_effective_sub_block_size(i, bv_src_sub, src_sub_size, false);
1527  // TODO: should it be set_array_max2 < set_array_max ????
1528  //if (set_array_max2 > set_array_max)
1529  if (set_array_max2 < set_array_max)
1530  set_array_max = set_array_max2;
1531  }
1532  }
1533  for (; j < set_array_max; ++j)
1534  {
1535  int is_res_full;
1536  digest_type digest = combine_and_sub(i, j,
1537  /*0,*/ bv_src_and, src_and_size,
1538  /*0,*/ bv_src_sub, src_sub_size,
1539  &is_res_full, false);
1540  if (digest)
1541  {
1542  unsigned block_bit_idx = 0;
1543  bool found = bm::bit_find_first(tb_ar_->tb1, &block_bit_idx, digest);
1544  BM_ASSERT(found);
1545  idx = bm::block_to_global_index(i, j, block_bit_idx);
1546  return found;
1547  }
1548  } // for j
1549  } // for i
1550  return false;
1551 }
1552 
1553 // ------------------------------------------------------------------------
1554 
1555 template<typename BV>
1556 unsigned
1558  unsigned i,
1559  const bvector_type_const_ptr* bv_src,
1560  size_t src_size,
1561  bool top_null_as_zero) BMNOEXCEPT
1562 {
1563  // quick hack to avoid scanning large, arrays, where such scan can be quite
1564  // expensive by itself (this makes this function approximate)
1565  if (src_size > 32)
1566  return bm::set_sub_array_size;
1567 
1568  unsigned max_size = 1;
1569  for (size_t k = 0; k < src_size; ++k)
1570  {
1571  const bvector_type* bv = bv_src[k];
1572  BM_ASSERT(bv);
1573  const typename bvector_type::blocks_manager_type& bman_arg =
1574  bv->get_blocks_manager();
1575  const bm::word_t* const* blk_blk_arg = bman_arg.get_topblock(i);
1576  if (!blk_blk_arg)
1577  {
1578  if (top_null_as_zero)
1579  return 0;
1580  continue;
1581  }
1582  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
1583  return bm::set_sub_array_size;
1584 
1585  for (unsigned j = bm::set_sub_array_size - 1; j > max_size; --j)
1586  {
1587  if (blk_blk_arg[j])
1588  {
1589  max_size = j;
1590  break;
1591  }
1592  } // for j
1593  if (max_size == bm::set_sub_array_size - 1)
1594  break;
1595  } // for k
1596  ++max_size;
1597  BM_ASSERT(max_size <= bm::set_sub_array_size);
1598 
1599  return max_size;
1600 }
1601 
1602 // ------------------------------------------------------------------------
1603 
1604 template<typename BV>
1606  const bvector_type_const_ptr* bv_src1,
1607  size_t src_size1,
1608  const bvector_type_const_ptr* bv_src2,
1609  size_t src_size2) BMNOEXCEPT
1610 {
1611  unsigned set_array_max = find_effective_sub_block_size(i, bv_src1, src_size1, true);
1612  if (set_array_max && src_size2)
1613  {
1614  unsigned set_array_max2 =
1615  find_effective_sub_block_size(i, bv_src2, src_size2, false);
1616  if (set_array_max2 > set_array_max) // TODO: use range intersect
1617  set_array_max = set_array_max2;
1618  }
1619  return set_array_max;
1620 }
1621 
1622 
1623 // ------------------------------------------------------------------------
1624 
1625 template<typename BV>
1626 void aggregator<BV>::combine_or(unsigned i, unsigned j,
1627  bvector_type& bv_target,
1628  const bvector_type_const_ptr* bv_src,
1629  size_t src_size)
1630 {
1631  typename bvector_type::blocks_manager_type& bman_target =
1632  bv_target.get_blocks_manager();
1633 
1634  ar_->reset_or_blocks();
1635  bm::word_t* blk = sort_input_blocks_or(/*0,*/ bv_src, src_size, i, j);
1636 
1637  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1638 
1639  if (blk == FULL_BLOCK_FAKE_ADDR) // nothing to do - golden block(!)
1640  {
1641  bman_target.check_alloc_top_subblock(i);
1642  bman_target.set_block_ptr(i, j, blk);
1643  if (++j == bm::set_sub_array_size)
1644  bman_target.validate_top_full(i);
1645  }
1646  else
1647  {
1648  size_t arg_blk_count = ar_->v_arg_or_blk.size();
1649  size_t arg_blk_gap_count = ar_->v_arg_or_blk_gap.size();
1650  if (arg_blk_count || arg_blk_gap_count)
1651  {
1652  bool all_one = process_bit_blocks_or(bman_target, i, j, *ar_);
1653  if (!all_one)
1654  {
1655  if (arg_blk_gap_count)
1656  process_gap_blocks_or(*ar_);
1657  // we have some results, allocate block and copy from temp
1658  bman_target.opt_copy_bit_block(i, j, tb_ar_->tb1,
1659  opt_mode_, tb_ar_->tb_opt);
1660  }
1661  }
1662  }
1663 }
1664 
1665 // ------------------------------------------------------------------------
1666 
1667 template<typename BV>
1668 void aggregator<BV>::combine_and(unsigned i, unsigned j,
1669  bvector_type& bv_target,
1670  const bvector_type_const_ptr* bv_src,
1671  size_t src_and_size)
1672 {
1673  BM_ASSERT(src_and_size);
1674 
1675  bm::word_t* blk = sort_input_blocks_and(/*0,*/ bv_src, src_and_size, i, j);
1676  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1677  if (!blk) // nothing to do - golden block(!)
1678  return;
1679 
1680  size_t arg_blk_and_count = ar_->v_arg_and_blk.size();
1681  size_t arg_blk_and_gap_count = ar_->v_arg_and_blk_gap.size();
1682  if (arg_blk_and_count || arg_blk_and_gap_count)
1683  {
1684  if (!arg_blk_and_gap_count && (arg_blk_and_count == 1))
1685  {
1686  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1687  {
1688  // another nothing to do: one FULL block
1689  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1690  bman_target.check_alloc_top_subblock(i);
1691  bman_target.set_block_ptr(i, j, blk);
1692  if (++j == bm::set_sub_array_size)
1693  bman_target.validate_top_full(i);
1694  return;
1695  }
1696  }
1697  // AND bit-blocks
1698  //
1699  bm::id64_t digest = process_bit_blocks_and(*ar_, ~0ull, true);
1700  if (!digest)
1701  return;
1702 
1703  // AND all GAP blocks (if any)
1704  //
1705  if (arg_blk_and_gap_count)
1706  digest = process_gap_blocks_and(*ar_, digest);
1707  if (digest) // we have results , allocate block and copy from temp
1708  {
1709  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1710  bman_target.opt_copy_bit_block(i, j, tb_ar_->tb1,
1711  opt_mode_, tb_ar_->tb_opt);
1712  }
1713  }
1714 }
1715 
1716 // ------------------------------------------------------------------------
1717 
1718 template<typename BV>
1721  unsigned i, unsigned j,
1722  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
1723  const bvector_type_const_ptr* bv_src_sub, size_t src_sub_size,
1724  int* is_result_full, bool find_all)
1725 {
1726  BM_ASSERT(is_result_full);
1727 
1728  is_single_bit_ = false;
1729  *is_result_full = 0;
1730  bm::word_t* blk = sort_input_blocks_and(/*and_idx,*/ bv_src_and, src_and_size, i, j);
1731  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1732  if (!blk)
1733  return 0; // nothing to do - golden block(!)
1734 
1735  {
1736  size_t arg_blk_and_count = ar_->v_arg_and_blk.size();
1737  size_t arg_blk_and_gap_count = ar_->v_arg_and_blk_gap.size();
1738  if (!(arg_blk_and_count | arg_blk_and_gap_count))
1739  return 0; // nothing to do - golden block(!)
1740 
1741  ar_->reset_or_blocks();
1742  if (src_sub_size)
1743  {
1744  blk = sort_input_blocks_or(/*sub_idx,*/ bv_src_sub, src_sub_size, i, j);
1745  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1746  if (blk == FULL_BLOCK_FAKE_ADDR)
1747  return 0; // nothing to do - golden block(!)
1748  }
1749  else
1750  {
1751  if (!arg_blk_and_gap_count && (arg_blk_and_count == 1))
1752  {
1753  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1754  {
1755  *is_result_full = 1;
1756  return ~0ull;
1757  }
1758  }
1759  }
1760  }
1761 
1762  // AND-SUB bit-blocks
1763  //
1764  digest_type digest = process_bit_blocks_and(*ar_, ~0ull, find_all);
1765  if (!digest)
1766  return digest;
1767  digest = process_bit_blocks_sub(*ar_, digest);
1768 
1769  // if just 1 bit left after bit-blocks processing we can
1770  // use short variant of GAP blocks AND-SUB
1771  //
1772  switch(bm::word_bitcount64(digest))
1773  {
1774  case 0:
1775  return digest;
1776  case 1:
1777  if (is_single_bit_)
1778  {
1779  size_t arg_blk_gap_count = ar_->v_arg_and_blk_gap.size();
1780  for (size_t k = 0; k < arg_blk_gap_count; ++k)
1781  if (!bm::gap_test_unr(ar_->v_arg_and_blk_gap[k], single_bit_idx_))
1782  return 0; // AND 0 causes result to turn 0
1783  arg_blk_gap_count = ar_->v_arg_or_blk_gap.size();
1784  for (size_t k = 0; k < arg_blk_gap_count; ++k)
1785  if (bm::gap_test_unr(ar_->v_arg_or_blk_gap[k], single_bit_idx_))
1786  return 0; // AND-NOT causes search result to turn 0
1787  return digest;
1788  }
1789  break;
1790  default: break;
1791  } // switch
1792 
1793  // AND all GAP block
1794  //
1795  digest = process_gap_blocks_and(*ar_, digest);
1796  if (!digest)
1797  return digest;
1798  digest = process_gap_blocks_sub(*ar_, digest);
1799 
1800  is_single_bit_ = false;
1801 
1802  return digest;
1803 }
1804 
1805 // ------------------------------------------------------------------------
1806 
1807 template<typename BV>
1809 {
1810  size_t arg_blk_gap_count = ar.v_arg_or_blk_gap.size();
1811  bm::word_t* blk = tb_ar_->tb1;
1812  for (size_t k = 0; k < arg_blk_gap_count; ++k)
1814 }
1815 
1816 // ------------------------------------------------------------------------
1817 
1818 template<typename BV>
1821  digest_type digest)
1822 {
1823  bm::word_t* blk = tb_ar_->tb1;
1824  const size_t arg_blk_gap_count = ar.v_arg_and_blk_gap.size();
1825 
1826  for (size_t k = 0; (k < arg_blk_gap_count) && digest; ++k)
1827  {
1828  digest = bm::gap_and_to_bitset(blk, ar.v_arg_and_blk_gap[k], digest);
1829  switch(bm::word_bitcount64(digest))
1830  {
1831  case 0:
1832  return digest;
1833  case 1:
1834  is_single_bit_ = bm::bit_find_first_if_1(blk, &single_bit_idx_, digest);
1835  if (is_single_bit_)
1836  {
1837  for (++k; k < arg_blk_gap_count; ++k)
1838  if (!bm::gap_test_unr(ar.v_arg_and_blk_gap[k], single_bit_idx_))
1839  return 0; // AND 0 causes result to turn 0
1840  return digest;
1841  }
1842  break;
1843  default: break;
1844  }
1845  } // for k
1846  BM_ASSERT(digest || bm::bit_is_all_zero(blk));
1847  return digest;
1848 }
1849 
1850 // ------------------------------------------------------------------------
1851 
1852 template<typename BV>
1855  digest_type digest)
1856 {
1857  const size_t arg_blk_gap_count = ar.v_arg_or_blk_gap.size();
1858  bm::word_t* blk = tb_ar_->tb1;
1859 
1860  if (is_single_bit_)
1861  {
1862  for (size_t k = 0; k < arg_blk_gap_count; ++k)
1863  if (bm::gap_test_unr(ar.v_arg_or_blk_gap[k], single_bit_idx_))
1864  return 0; // AND-NOT causes search result to turn 0
1865  return digest;
1866  }
1867 
1868  for (size_t k = 0; digest && (k < arg_blk_gap_count); ++k)
1869  {
1870  digest = bm::gap_sub_to_bitset(blk, ar.v_arg_or_blk_gap[k], digest);
1871  switch(bm::word_bitcount64(digest))
1872  {
1873  case 0:
1874  return digest;
1875  case 1:
1876  is_single_bit_ = bm::bit_find_first_if_1(blk, &single_bit_idx_, digest);
1877  if (is_single_bit_)
1878  {
1879  for (++k; k < arg_blk_gap_count; ++k)
1880  if (bm::gap_test_unr(ar.v_arg_or_blk_gap[k], single_bit_idx_))
1881  return 0; // AND-NOT causes search result to turn 0
1882  return digest;
1883  }
1884  break;
1885  default: break;
1886  }
1887  } // for k
1888  BM_ASSERT(digest || bm::bit_is_all_zero(blk));
1889  return digest;
1890 }
1891 
1892 // ------------------------------------------------------------------------
1893 
1894 template<typename BV>
1895 bool aggregator<BV>::test_gap_blocks_and(size_t arg_blk_gap_count,
1896  unsigned bit_idx)
1897 {
1898  unsigned b = 1;
1899  for (size_t i = 0; i < arg_blk_gap_count && b; ++i)
1900  b = bm::gap_test_unr(ar_->v_arg_and_blk_gap[i], bit_idx);
1901  return b;
1902 }
1903 
1904 // ------------------------------------------------------------------------
1905 
1906 template<typename BV>
1907 bool aggregator<BV>::test_gap_blocks_sub(size_t arg_blk_gap_count,
1908  unsigned bit_idx)
1909 {
1910  unsigned b = 1;
1911  for (size_t i = 0; i < arg_blk_gap_count; ++i)
1912  {
1913  b = bm::gap_test_unr(ar_->v_arg_or_blk_gap[i], bit_idx);
1914  if (b)
1915  return false;
1916  }
1917  return true;
1918 }
1919 
1920 // ------------------------------------------------------------------------
1921 
1922 
1923 template<typename BV>
1925  unsigned i, unsigned j,
1926  const arena& ar)
1927 {
1928  size_t arg_blk_count = ar.v_arg_or_blk.size();
1929  bm::word_t* blk = tb_ar_->tb1;
1930  bool all_one;
1931 
1932  size_t k = 0;
1933 
1934  if (arg_blk_count) // copy the first block
1935  bm::bit_block_copy(blk, ar.v_arg_or_blk[k++]);
1936  else
1937  bm::bit_block_set(blk, 0);
1938 
1939  // process all BIT blocks
1940  //
1941  size_t unroll_factor, len, len_unr;
1942 
1943  unroll_factor = 4;
1944  len = arg_blk_count - k;
1945  len_unr = len - (len % unroll_factor);
1946  for( ;k < len_unr; k+=unroll_factor)
1947  {
1948  all_one = bm::bit_block_or_5way(blk,
1949  ar.v_arg_or_blk[k], ar.v_arg_or_blk[k+1],
1950  ar.v_arg_or_blk[k+2], ar.v_arg_or_blk[k+3]);
1951  if (all_one)
1952  {
1953  BM_ASSERT(blk == tb_ar_->tb1);
1955  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1956  return true;
1957  }
1958  } // for k
1959 
1960  unroll_factor = 2;
1961  len = arg_blk_count - k;
1962  len_unr = len - (len % unroll_factor);
1963  for( ;k < len_unr; k+=unroll_factor)
1964  {
1965  all_one = bm::bit_block_or_3way(blk, ar.v_arg_or_blk[k], ar.v_arg_or_blk[k+1]);
1966  if (all_one)
1967  {
1968  BM_ASSERT(blk == tb_ar_->tb1);
1970  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1971  return true;
1972  }
1973  } // for k
1974 
1975  for (; k < arg_blk_count; ++k)
1976  {
1977  all_one = bm::bit_block_or(blk, ar.v_arg_or_blk[k]);
1978  if (all_one)
1979  {
1980  BM_ASSERT(blk == tb_ar_->tb1);
1982  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1983  return true;
1984  }
1985  } // for k
1986 
1987  return false;
1988 }
1989 
1990 // ------------------------------------------------------------------------
1991 
1992 template<typename BV>
1995  digest_type digest,
1996  bool find_all)
1997 {
1998  bm::word_t* blk = tb_ar_->tb1;
1999  size_t arg_blk_count = ar.v_arg_and_blk.size();
2000  const word_t** args = ar.v_arg_and_blk.data();
2001 
2002  size_t k = 0;
2003 
2004  block_idx_type nb_from = (range_from_ >> bm::set_block_shift);
2005  block_idx_type nb_to = (range_to_ >> bm::set_block_shift);
2006  if (range_set_ && (nb_from == nb_to))
2007  {
2008  unsigned nbit_from = unsigned(range_from_ & bm::set_block_mask);
2009  unsigned nbit_to = unsigned(range_to_ & bm::set_block_mask);
2010  digest_type digest0 = bm::digest_mask(nbit_from, nbit_to);
2011  digest &= digest0;
2012 
2013  if (arg_blk_count > 1) // 2 or more
2014  {
2015  if (find_all)
2016  digest = bm::bit_block_init_and_2way(blk,
2017  args[k], args[k+1],
2018  digest);
2019  else
2020  digest = bm::bit_block_and_2way(blk,
2021  args[k], args[k+1], digest);
2022  k += 2;
2023  }
2024  else
2025  {
2026  bm::block_init_digest0(blk, digest);
2027  }
2028  }
2029  else
2030  {
2031  switch (arg_blk_count)
2032  {
2033  case 0:
2034  bm::block_init_digest0(blk, digest); // 0xFF... by default
2035  return digest;
2036  case 1:
2037  bm::bit_block_copy(blk, args[k]);
2038  return bm::calc_block_digest0(blk);
2039  default:
2040  digest = bm::bit_block_and_2way(blk, args[k], args[k+1], ~0ull);
2041  k += 2;
2042  break;
2043  } // switch
2044  }
2045 
2046  const size_t unroll_factor = 4;
2047  for (; k + unroll_factor < arg_blk_count; k += unroll_factor)
2048  {
2049  digest = bm::bit_block_and_5way(blk,
2050  args[k], args[k+1], args[k+2], args[k+3],
2051  digest);
2052  switch (bm::word_bitcount64(digest))
2053  {
2054  case 0: return 0;
2055  case 1:
2056  is_single_bit_ = bm::bit_find_first_if_1(blk, &single_bit_idx_, digest);
2057  if (is_single_bit_)
2058  {
2059  k += unroll_factor;
2060  sbit_check:
2061  const unsigned nword = unsigned(single_bit_idx_ >> bm::set_word_shift);
2062  const unsigned mask = 1u << (single_bit_idx_ & bm::set_word_mask);
2063  for (; k + unroll_factor < arg_blk_count; k += unroll_factor)
2064  {
2065  bm::word_t acc = mask & args[k][nword] & args[k+1][nword] &
2066  args[k+2][nword] & args[k+3][nword];
2067  if (!acc)
2068  return 0;
2069  } // for k
2070  for (; k + 2 < arg_blk_count; k += 2)
2071  {
2072  bm::word_t acc = mask & args[k][nword] & args[k+1][nword];
2073  if (!acc)
2074  return 0;
2075  } // for k
2076 
2077  bm::word_t acc = mask;
2078  for (; k < arg_blk_count; ++k)
2079  acc &= args[k][nword];
2080  if (!(mask & acc))
2081  return 0;
2082  return digest;
2083  }
2084  break;
2085  default: break;
2086  } // switch
2087  } // for k
2088 
2089  for (; k + 2 < arg_blk_count; k += 2)
2090  {
2091  digest = bm::bit_block_and_3way(blk, args[k], args[k+1], digest);
2092  switch(bm::word_bitcount64(digest))
2093  {
2094  case 0: return digest;
2095  case 1:
2096  is_single_bit_ = bm::bit_find_first_if_1(blk,
2097  &single_bit_idx_, digest);
2098  if (is_single_bit_) { ++k; goto sbit_check; }
2099  break;
2100  default: break;
2101  } // switch
2102  }
2103  for (; k < arg_blk_count; ++k)
2104  {
2105  digest = bm::bit_block_and(blk, args[k], digest);
2106  switch(bm::word_bitcount64(digest))
2107  {
2108  case 0: return digest;
2109  case 1:
2110  is_single_bit_ = bm::bit_find_first_if_1(blk,
2111  &single_bit_idx_, digest);
2112  if (is_single_bit_)
2113  { ++k; goto sbit_check; }
2114  break;
2115  default: break;
2116  } // switch
2117  } // for k
2118  return digest;
2119 }
2120 
2121 // ------------------------------------------------------------------------
2122 
2123 template<typename BV>
2126  digest_type digest)
2127 {
2128  size_t arg_blk_count = ar.v_arg_or_blk.size();
2129  bm::word_t* blk = tb_ar_->tb1;
2130  const word_t** args = ar.v_arg_or_blk.data();
2131 
2132  const size_t unroll_factor = 4;
2133  size_t k = 0;
2134 
2135  if (is_single_bit_)
2136  goto sbit_check;
2137 
2138  for (; k + unroll_factor < arg_blk_count; k += unroll_factor)
2139  {
2140  digest = bm::bit_block_sub_5way(blk,
2141  args[k], args[k+1],args[k+2], args[k+3],
2142  digest);
2143  switch(bm::word_bitcount64(digest))
2144  {
2145  case 0:
2146  return digest;
2147  case 1:
2148  is_single_bit_ = bm::bit_find_first_if_1(blk,
2149  &single_bit_idx_, digest);
2150  if (is_single_bit_)
2151  {
2152  k += unroll_factor;
2153  sbit_check:
2154  const unsigned mask =
2155  1u << (single_bit_idx_ & bm::set_word_mask);
2156  const unsigned nword =
2157  unsigned(single_bit_idx_ >> bm::set_word_shift);
2158  bm::word_t acc = 0;
2159  for (; k + unroll_factor < arg_blk_count; k += unroll_factor)
2160  {
2161  acc = args[k][nword] | args[k+1][nword] |
2162  args[k+2][nword] | args[k+3][nword];
2163  if (mask & acc)
2164  return 0;
2165  } // for k
2166  for (; k < arg_blk_count; ++k)
2167  acc |= args[k][nword];
2168  if (mask & acc)
2169  return 0;
2170  return digest;
2171  }
2172  break;
2173  default: break;
2174  } // switch
2175  } // for k
2176  for (; k + 2 < arg_blk_count; k += 2)
2177  {
2178  digest = bm::bit_block_sub_3way(blk, args[k], args[k+1], digest);
2179  switch(bm::word_bitcount64(digest))
2180  {
2181  case 0: return digest;
2182  case 1:
2183  is_single_bit_ = bm::bit_find_first_if_1(blk,
2184  &single_bit_idx_, digest);
2185  if (is_single_bit_) { ++k; goto sbit_check; }
2186  break;
2187  default: break;
2188  } // switch
2189  }
2190  for (; k < arg_blk_count; ++k)
2191  {
2192  digest = bm::bit_block_sub(blk, args[k], digest);
2193  switch(bm::word_bitcount64(digest))
2194  {
2195  case 0: return digest;
2196  case 1:
2197  is_single_bit_ = bm::bit_find_first_if_1(blk, &single_bit_idx_, digest);
2198  if (is_single_bit_)
2199  { ++k; goto sbit_check; }
2200  break;
2201  default: break;
2202  } // switch
2203  } // for
2204  return digest;
2205 }
2206 
2207 // ------------------------------------------------------------------------
2208 
2209 template<typename BV>
2211  const bvector_type_const_ptr* bv_src, size_t src_size,
2212  bool init_clear)
2213 {
2214  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
2215  if (init_clear)
2216  {
2217  if (bman_target.is_init())
2218  bman_target.deinit_tree();
2219  }
2220 
2221  unsigned top_blocks = bman_target.top_block_size();
2222  size_type size = bv_target.size();
2223  bool need_realloc = false;
2224 
2225  // pre-scan to do target size harmonization
2226  for (unsigned i = 0; i < src_size; ++i)
2227  {
2228  const bvector_type* bv = bv_src[i];
2229  BM_ASSERT(bv);
2230  const typename bvector_type::blocks_manager_type& bman_arg =
2231  bv->get_blocks_manager();
2232  unsigned arg_top_blocks = bman_arg.top_block_size();
2233  if (arg_top_blocks > top_blocks)
2234  {
2235  need_realloc = true;
2236  top_blocks = arg_top_blocks;
2237  }
2238  size_type arg_size = bv->size();
2239  if (arg_size > size)
2240  size = arg_size;
2241  } // for i
2242 
2243  if (need_realloc)
2244  bman_target.reserve_top_blocks(top_blocks);
2245  if (!bman_target.is_init())
2246  bman_target.init_tree();
2247  if (size > bv_target.size())
2248  bv_target.resize(size);
2249 
2250  return top_blocks;
2251 }
2252 
2253 // ------------------------------------------------------------------------
2254 
2255 template<typename BV>
2256 unsigned
2258  size_t src_size) BMNOEXCEPT
2259 {
2260  unsigned top_blocks = 1;
2261  for (unsigned i = 0; i < src_size; ++i) // pre-scan: target size sync
2262  {
2263  if (const bvector_type* bv = bv_src[i])
2264  {
2265  const typename bvector_type::blocks_manager_type& bman_arg =
2266  bv->get_blocks_manager();
2267  unsigned arg_top_blocks = bman_arg.top_block_size();
2268  if (arg_top_blocks > top_blocks)
2269  top_blocks = arg_top_blocks;
2270  }
2271  } // for i
2272  return top_blocks;
2273 }
2274 
2275 // ------------------------------------------------------------------------
2276 
2277 template<typename BV>
2279  const bvector_type_const_ptr* bv_src,
2280  size_t src_size,
2281  unsigned i, unsigned j)
2282 {
2283  auto bit_arr = ar_->v_arg_or_blk.resize_no_copy(src_size);
2284  auto gap_arr = ar_->v_arg_or_blk_gap.resize_no_copy(src_size);
2285 
2286  size_t bc(0), gc(0);
2287 
2288  for (size_t k = 0; k < src_size; ++k)
2289  {
2290  const bm::word_t* arg_blk =
2291  bv_src[k]->get_blocks_manager().get_block_ptr(i, j);
2292  if (BM_IS_GAP(arg_blk))
2293  {
2294  gap_arr[gc++] = BMGAP_PTR(arg_blk);
2295  }
2296  else // FULL or bit block
2297  {
2298  if (!arg_blk)
2299  continue;
2300  if (arg_blk == FULL_BLOCK_FAKE_ADDR)
2301  return FULL_BLOCK_FAKE_ADDR;
2302  bit_arr[bc++] = arg_blk;
2303  }
2304  } // for k
2305 
2306  ar_->v_arg_or_blk.resize_no_check(bc);
2307  ar_->v_arg_or_blk_gap.resize_no_check(gc);
2308 
2309  return 0;
2310 }
2311 
2312 // ------------------------------------------------------------------------
2313 
2314 template<typename BV>
2316  const bvector_type_const_ptr* bv_src,
2317  size_t src_size,
2318  unsigned i, unsigned j)
2319 {
2320  ar_->v_arg_tmp_blk.resize_no_copy(src_size);
2321 
2322  auto blocks_arr = ar_->v_arg_tmp_blk.data();
2323  for (size_t k = 0; k < src_size; ++k)
2324  {
2325  const bm::word_t* arg_blk = blocks_arr[k] =
2326  bv_src[k]->get_blocks_manager().get_block_ptr(i, j);
2327  if (!arg_blk)
2328  return 0;
2329  }
2330 
2331  bool has_full_blk = false;
2332  auto bit_arr = ar_->v_arg_and_blk.resize_no_copy(src_size + 1);
2333  auto gap_arr = ar_->v_arg_and_blk_gap.resize_no_copy(src_size + 1);
2334  size_t bc(0), gc(0);
2335 
2336  for (size_t k = 0; k < src_size; ++k)
2337  {
2338  const bm::word_t* arg_blk = blocks_arr[k];
2339  if (BM_IS_GAP(arg_blk))
2340  {
2341  const bm::gap_word_t* gap_blk = BMGAP_PTR(arg_blk);
2342  gap_arr[gc++] = gap_blk;
2343  continue;
2344  }
2345  // FULL or bit block
2346  if (arg_blk == FULL_BLOCK_FAKE_ADDR)
2347  {
2348  has_full_blk = true;
2349  continue;
2350  }
2351  bit_arr[bc++] = arg_blk;
2352  } // for k
2353 
2354  if (range_gap_blk_[0]) // block specific AND filter exists
2355  {
2356  BM_ASSERT(range_set_);
2357  gap_arr[gc++] = range_gap_blk_;
2358  }
2359  ar_->v_arg_and_blk_gap.resize_no_check(gc);
2360 
2361  if (has_full_blk && (!bc && !gc))
2362  bit_arr[bc++] = FULL_BLOCK_REAL_ADDR;
2363  ar_->v_arg_and_blk.resize_no_check(bc);
2364 
2365  return FULL_BLOCK_FAKE_ADDR;
2366 }
2367 
2368 // ------------------------------------------------------------------------
2369 
2370 template<typename BV>
2372  const size_t* src_idx,
2373  size_t k,
2374  unsigned i, unsigned j)
2375 {
2376  BM_ASSERT(bcache_ptr_);
2377  BM_ASSERT(src_idx);
2378 
2379  size_t bv_idx = src_idx[k];
2380  auto cnt = bcache_ptr_->cnt_vect_[bv_idx];
2381  if (cnt > 0) // frequent bector
2382  {
2383  bm::word_t* bit_blk = bcache_ptr_->blk_vect_[bv_idx];
2384  bm::pair<unsigned, unsigned> pair_ij = bcache_ptr_->blk_ij_vect_[bv_idx];
2385  if (!bit_blk)
2386  {
2388  pair_ij.first = i+1; // make it NOT match
2389  bcache_ptr_->blk_vect_[bv_idx] = bit_blk;
2390  }
2391  // block is allocated
2392  if (i != pair_ij.first || j != pair_ij.second) // not NB cached?
2393  {
2394  bm::gap_convert_to_bitset(bit_blk, BMGAP_PTR(arg_blk));
2395  pair_ij.first = i; pair_ij.second = j;
2396  bcache_ptr_->blk_ij_vect_[bv_idx] = pair_ij;
2397  }
2398  ++gap_cache_cnt_;
2399  return bit_blk; // use cached bit-block for operation
2400  }
2401  return 0;
2402 }
2403 
2404 // ------------------------------------------------------------------------
2405 
2406 template<typename BV>
2408  const bvector_type_const_ptr* bv_src, size_t src_size)
2409 {
2410  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
2411  BM_ASSERT(src_size);
2412 
2413  if (src_size == 0)
2414  {
2415  bv_target.clear();
2416  return;
2417  }
2418  const bvector_type* bv = bv_src[0];
2419  bv_target.copy(*bv, bm::finalization::READWRITE);
2420  for (unsigned i = 1; i < src_size; ++i)
2421  {
2422  bv = bv_src[i];
2423  BM_ASSERT(bv);
2424  bv_target.bit_or(*bv);
2425  }
2426 }
2427 
2428 // ------------------------------------------------------------------------
2429 
2430 template<typename BV>
2432  const bvector_type_const_ptr* bv_src, size_t src_size)
2433 {
2434  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
2435  BM_ASSERT(src_size);
2436 
2437  if (src_size == 0)
2438  {
2439  bv_target.clear();
2440  return;
2441  }
2442  const bvector_type* bv = bv_src[0];
2443  bv_target.copy(*bv, bm::finalization::READWRITE);
2444 
2445  for (unsigned i = 1; i < src_size; ++i)
2446  {
2447  bv = bv_src[i];
2448  BM_ASSERT(bv);
2449  bv_target.bit_and(*bv);
2450  }
2451 }
2452 
2453 // ------------------------------------------------------------------------
2454 
2455 template<typename BV>
2457  const bvector_type_const_ptr* bv_src_and,
2458  size_t src_and_size,
2459  const bvector_type_const_ptr* bv_src_sub,
2460  size_t src_sub_size)
2461 {
2462  BM_ASSERT(src_and_size);
2463  BM_ASSERT(!bv_target.is_ro()); // immutable vector used as a target
2464 
2465  combine_and_horizontal(bv_target, bv_src_and, src_and_size);
2466 
2467  for (unsigned i = 0; i < src_sub_size; ++i)
2468  {
2469  const bvector_type* bv = bv_src_sub[i];
2470  BM_ASSERT(bv);
2471  bv_target -= *bv;
2472  }
2473 }
2474 
2475 // ------------------------------------------------------------------------
2476 
2477 template<typename BV>
2479  const bvector_type_const_ptr* bv_src,
2480  size_t src_size)
2481 {
2482  top_block_size_ = resize_target(bv_target, bv_src, src_size);
2483 
2484  // set initial carry overs all to 0
2485  ar_->carry_overs.resize(src_size);
2486  for (unsigned i = 0; i < src_size; ++i) // reset co flags
2487  ar_->carry_overs[i] = 0;
2488 }
2489 
2490 // ------------------------------------------------------------------------
2491 
2492 template<typename BV>
2494  bvector_type& bv_target,
2495  const bvector_type_const_ptr* bv_src_and, size_t src_and_size,
2496  bool any)
2497 {
2498  if (!src_and_size)
2499  {
2500  bv_target.clear();
2501  return false;
2502  }
2503  prepare_shift_right_and(bv_target, bv_src_and, src_and_size);
2504 
2505  for (unsigned i = 0; i < bm::set_top_array_size; ++i)
2506  {
2507  if (i > top_block_size_)
2508  {
2509  if (!any_carry_overs(ar_->carry_overs.data(), src_and_size))
2510  break; // quit early if there is nothing to carry on
2511  }
2512 
2513  unsigned j = 0;
2514  do
2515  {
2516  bool found =
2517  combine_shift_right_and(i, j, bv_target, bv_src_and, src_and_size);
2518  if (found && any)
2519  return found;
2520  } while (++j < bm::set_sub_array_size);
2521 
2522  } // for i
2523 
2524  if (compute_count_)
2525  return bool(count_);
2526 
2527  return bv_target.any();
2528 }
2529 
2530 // ------------------------------------------------------------------------
2531 
2532 template<typename BV>
2533 bool aggregator<BV>::combine_shift_right_and(unsigned i, unsigned j,
2534  bvector_type& bv_target,
2535  const bvector_type_const_ptr* bv_src,
2536  size_t src_size)
2537 {
2538  bm::word_t* blk = temp_blk_ ? temp_blk_ : tb_ar_->tb1;
2539  unsigned char* carry_overs = ar_->carry_overs.data();
2540 
2541  bm::id64_t digest = ~0ull; // start with a full content digest
2542 
2543  bool blk_zero = false;
2544  // first initial block is just copied over from the first AND
2545  {
2546  const blocks_manager_type& bman_arg = bv_src[0]->get_blocks_manager();
2547  BM_ASSERT(bman_arg.is_init());
2548  const bm::word_t* arg_blk = bman_arg.get_block(i, j);
2549  if (BM_IS_GAP(arg_blk))
2550  {
2551  bm::bit_block_set(blk, 0);
2552  bm::gap_add_to_bitset(blk, BMGAP_PTR(arg_blk));
2553  }
2554  else
2555  {
2556  if (arg_blk)
2557  {
2558  bm::bit_block_copy(blk, arg_blk);
2559  }
2560  else
2561  {
2562  blk_zero = true; // set flag for delayed block init
2563  digest = 0;
2564  }
2565  }
2566  carry_overs[0] = 0;
2567  }
2568 
2569  for (unsigned k = 1; k < src_size; ++k)
2570  {
2571  unsigned carry_over = carry_overs[k];
2572  if (!digest && !carry_over) // 0 into "00000" block >> 0
2573  continue;
2574  if (blk_zero) // delayed temp block 0-init requested
2575  {
2576  bm::bit_block_set(blk, 0);
2577  blk_zero = !blk_zero; // = false
2578  }
2579  const bm::word_t* arg_blk = get_arg_block(bv_src, k, i, j);
2580  carry_overs[k] = (unsigned char)
2581  process_shift_right_and(blk, arg_blk, digest, carry_over);
2582  BM_ASSERT(carry_overs[k] == 0 || carry_overs[k] == 1);
2583  } // for k
2584 
2585  if (blk_zero) // delayed temp block 0-init
2586  {
2587  bm::bit_block_set(blk, 0);
2588  }
2589  // block now gets emitted into the target bit-vector
2590  if (digest)
2591  {
2593 
2594  if (compute_count_)
2595  {
2596  unsigned cnt = bm::bit_block_count(blk, digest);
2597  count_ += cnt;
2598  }
2599  else
2600  {
2601  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
2602  bman_target.opt_copy_bit_block(i, j, blk, opt_mode_, tb_ar_->tb_opt);
2603  }
2604  return true;
2605  }
2606  return false;
2607 }
2608 
2609 // ------------------------------------------------------------------------
2610 
2611 template<typename BV>
2613  bm::word_t* BMRESTRICT blk,
2614  const bm::word_t* BMRESTRICT arg_blk,
2615  digest_type& BMRESTRICT digest,
2616  unsigned carry_over) BMNOEXCEPT
2617 {
2618  BM_ASSERT(carry_over == 1 || carry_over == 0);
2619 
2620  if (BM_IS_GAP(arg_blk)) // GAP argument
2621  {
2622  if (digest)
2623  {
2624  carry_over =
2625  bm::bit_block_shift_r1_and_unr(blk, carry_over,
2626  FULL_BLOCK_REAL_ADDR, &digest);
2627  }
2628  else // digest == 0, but carry_over can change that
2629  {
2630  blk[0] = carry_over;
2631  carry_over = 0;
2632  digest = blk[0]; // NOTE: this does NOT account for AND (yet)
2633  }
2634  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
2635 
2636  digest = bm::gap_and_to_bitset(blk, BMGAP_PTR(arg_blk), digest);
2637  //digest = bm::update_block_digest0(blk, digest);
2638  }
2639  else // 2 bit-blocks
2640  {
2641  if (arg_blk) // use fast fused SHIFT-AND operation
2642  {
2643  if (digest)
2644  {
2645  carry_over =
2646  bm::bit_block_shift_r1_and_unr(blk, carry_over, arg_blk,
2647  &digest);
2648  }
2649  else // digest == 0
2650  {
2651  blk[0] = carry_over & arg_blk[0];
2652  carry_over = 0;
2653  digest = blk[0];
2654  }
2655  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
2656  }
2657  else // arg is zero - target block => zero
2658  {
2659  carry_over = blk[bm::set_block_size-1] >> 31; // carry out
2660  if (digest)
2661  {
2662  bm::bit_block_set(blk, 0); // TODO: digest based set
2663  digest = 0;
2664  }
2665  }
2666  }
2667  return carry_over;
2668 }
2669 
2670 // ------------------------------------------------------------------------
2671 
2672 template<typename BV>
2674  const bvector_type_const_ptr* bv_src,
2675  unsigned k, unsigned i, unsigned j) BMNOEXCEPT
2676 {
2677  return bv_src[k]->get_blocks_manager().get_block(i, j);
2678 }
2679 
2680 // ------------------------------------------------------------------------
2681 
2682 template<typename BV>
2683 bool aggregator<BV>::any_carry_overs(const unsigned char* carry_overs,
2684  size_t co_size) BMNOEXCEPT
2685 {
2686  // TODO: loop unroll?
2687  unsigned acc = carry_overs[0];
2688  for (size_t i = 1; i < co_size; ++i)
2689  acc |= carry_overs[i];
2690  return acc;
2691 }
2692 
2693 // ------------------------------------------------------------------------
2694 
2695 template<typename BV>
2697 {
2698  bvector_type* bv_target = check_create_target(); // create target vector
2699  BM_ASSERT(bv_target);
2700 
2701  temp_blk_ = temp_block;
2702 
2703  switch (operation_)
2704  {
2705  case BM_NOT_DEFINED:
2706  break;
2707  case BM_SHIFT_R_AND:
2708  prepare_shift_right_and(*bv_target, ag_.arg_bv0.data(), ag_.arg_bv0.size());//arg_group0_size);
2709  operation_status_ = operation_status::op_prepared;
2710  break;
2711  default:
2712  BM_ASSERT(0);
2713  } // switch
2714 }
2715 
2716 // ------------------------------------------------------------------------
2717 
2718 template<typename BV>
2720 aggregator<BV>::run_step(unsigned i, unsigned j)
2721 {
2722  BM_ASSERT(operation_status_ == operation_status::op_prepared
2723  || operation_status_ == operation_status::op_in_progress);
2725 
2726  switch (operation_)
2727  {
2728  case BM_NOT_DEFINED:
2729  break;
2730 
2731  case BM_SHIFT_R_AND:
2732  {
2733  if (i > top_block_size_)
2734  {
2735  if (!this->any_carry_overs(ar_->carry_overs.data(), ag_.arg_bv0.size()))//arg_group0_size))
2736  {
2737  operation_status_ = operation_status::op_done;
2738  return operation_status_;
2739  }
2740  }
2741  //bool found =
2742  this->combine_shift_right_and(i, j, *bv_target_,
2743  ag_.arg_bv0.data(), ag_.arg_bv0.size());//arg_group0_size);
2744  operation_status_ = operation_status::op_in_progress;
2745  }
2746  break;
2747  default:
2748  BM_ASSERT(0);
2749  break;
2750  } // switch
2751 
2752  return operation_status_;
2753 }
2754 
2755 
2756 // ------------------------------------------------------------------------
2757 // aggregator::pipeline
2758 // ------------------------------------------------------------------------
2759 
2760 template<typename BV> template<class Opt>
2762 {
2763  size_t sz = arg_vect_.size();
2764  arg_groups** arr = arg_vect_.data();
2765  for (size_t i = 0; i < sz; ++i)
2766  free_arg_group(arr[i]);
2767  sz = bv_res_vect_.size();
2768  bvector_type** bv_arr = bv_res_vect_.data();
2769  for (size_t i = 0; i < sz; ++i)
2770  {
2771  bvector_type* bv = bv_arr[i];
2772  delete bv;
2773  } // for i
2774  sz = bcache_.blk_vect_.size();
2775  bm::word_t** blk_arr = bcache_.blk_vect_.data();
2776  for (size_t i = 0; i < sz; ++i)
2777  bm::aligned_free(blk_arr[i]);
2778 }
2779 
2780 // ------------------------------------------------------------------------
2781 
2782 template<typename BV> template<class Opt>
2784 {
2785  if (is_complete_)
2786  return;
2787 
2788  if constexpr (Opt::is_make_results())
2789  {
2790  BM_ASSERT(!bv_res_vect_.size());
2791  size_t sz = arg_vect_.size();
2792  bv_res_vect_.resize(sz);
2793  bvector_type** bv_arr = bv_res_vect_.data();
2794  for (size_t i = 0; i < sz; ++i)
2795  bv_arr[i] = 0;
2796  }
2797  if constexpr (Opt::is_compute_counts())
2798  {
2799  size_t sz = arg_vect_.size();
2800  count_res_vect_.resize(sz);
2801  size_type* cnt_arr = count_res_vect_.data();
2802  ::memset(cnt_arr, 0, sz * sizeof(cnt_arr[0]));
2803  }
2804 
2805  const arg_vector_type& pipe_args = get_args_vector();
2806  size_t pipe_size = pipe_args.size();
2807 
2808  for (size_t p = 0; p < pipe_size; ++p)
2809  {
2810  arg_groups* ag = pipe_args[p];
2811  complete_arg_group(ag);
2812 
2813  const bvector_type_const_ptr* bv_src_and = ag->arg_bv0.data();
2814  size_t src_and_size = ag->arg_bv0.size();
2815  unsigned top_blocks1 = max_top_blocks(bv_src_and, src_and_size);
2816  if (top_blocks1 > top_blocks_)
2817  top_blocks_ = top_blocks1;
2818 
2819  const bvector_type_const_ptr* bv_src_sub = ag->arg_bv1.data();
2820  size_t src_sub_size = ag->arg_bv1.size();
2821  unsigned top_blocks2 = max_top_blocks(bv_src_sub, src_sub_size);
2822  if (top_blocks2 > top_blocks_)
2823  top_blocks_ = top_blocks2;
2824 
2825  } // for p
2826  is_complete_ = true;
2827 
2828  BM_ASSERT(bcache_.bv_inp_vect_.size() == bcache_.cnt_vect_.size());
2829  BM_ASSERT(bcache_.bv_inp_vect_.size() == bcache_.blk_vect_.size());
2830  BM_ASSERT(bcache_.bv_inp_vect_.size() == bcache_.blk_ij_vect_.size());
2831 }
2832 
2833 // ------------------------------------------------------------------------
2834 
2835 template<typename BV> template<class Opt>
2837 {
2838  BM_ASSERT(ag);
2839  auto sz = ag->arg_bv0.size();
2840  total_vect_ += sz;
2841  complete_arg_sub_group(ag->arg_idx0, ag->arg_bv0.data(), sz);
2842  sz = ag->arg_bv1.size();
2843  total_vect_ += sz;
2844  complete_arg_sub_group(ag->arg_idx1, ag->arg_bv1.data(), sz);
2845 }
2846 
2847 // ------------------------------------------------------------------------
2848 
2849 template<typename BV> template<class Opt>
2851  index_vector_type& idx_vect,
2852  const bvector_type_const_ptr* bv_src, size_t size)
2853 {
2854  BM_ASSERT(idx_vect.size() == 0);
2855 
2856  for (size_t k = 0; k < size; ++k)
2857  {
2858  bool found(false); size_t bv_idx(0);
2859  const bvector_type* bv = bv_src[k];
2860  if (bv)
2861  {
2862  const bvector_type** bv_arr = bcache_.bv_inp_vect_.data();
2863  found =
2864  bm::find_ptr((void**)bv_arr, bcache_.bv_inp_vect_.size(),
2865  bv, &bv_idx);
2866  }
2867  if (found)
2868  bcache_.cnt_vect_[bv_idx]++; // increment vector usage counter
2869  else // not found (new one!)
2870  {
2871  bv_idx = bcache_.bv_inp_vect_.size();
2872  bcache_.bv_inp_vect_.push_back(bv); // register a new bv (0-cnt)
2873  bcache_.cnt_vect_.push_back(0);
2874  bcache_.blk_vect_.push_back(0); // NULL ptr
2875  bcache_.blk_ij_vect_.push_back(bm::pair<unsigned, unsigned>(0u, 0u));
2876  }
2877  // each arg group
2878  idx_vect.push_back(bv_idx);
2879  } // for k
2880 
2881  BM_ASSERT(idx_vect.size() == size);
2882 }
2883 
2884 // ------------------------------------------------------------------------
2885 
2886 template<typename BV> template<class Opt>
2889 {
2890  BM_ASSERT(!is_complete_);
2891  arg_groups* arg = construct_arg_group();
2892  arg_vect_.push_back(arg);
2893  return arg;
2894 }
2895 
2896 // ------------------------------------------------------------------------
2897 
2898 template<typename BV> template<class Opt>
2900 {
2901  const size_t cache_size = 256 * 1024; // estimation-speculation (L2)
2902  // ad-hoc estimate (not correct!) uses 2/3 of bit-vectors size (some are GAPs)
2903  // TODO: need to use real sparse vector statistics (AVG block size)
2904  //
2905  const float block_size = 0.75f * (bm::set_block_size * sizeof(bm::word_t));
2906  const float bv_struct_overhead = (64 * 8); // 8 cache lines in bytes
2907  const float cached_vect = float(cache_size) / float(block_size + bv_struct_overhead);
2908 
2909  size_t bv_count = unique_vectors();
2910  size_t args_total = arg_vect_.size(); // number of arg groups
2911  if ((bv_count < cached_vect) || (args_total < 2)) // worst case fit in L2
2912  return args_total;
2913 
2914  size_t avg_vect_per_group = total_vect_ / args_total;
2915 
2916  const float reuse_coeff = 0.7f; // spec. coeff of resue of vectors
2917  float f_batch_size =
2918  (1+reuse_coeff)*(float(avg_vect_per_group) / float(cached_vect) + 0.99f);
2919  size_t batch_size = size_t(f_batch_size);
2920 
2921  return batch_size;
2922 }
2923 
2924 
2925 // ------------------------------------------------------------------------
2926 // Arg Groups
2927 // ------------------------------------------------------------------------
2928 
2929 template<typename BV>
2931  unsigned agr_group)
2932 {
2933  BM_ASSERT_THROW(agr_group <= 1, BM_ERR_RANGE);
2934  BM_ASSERT(agr_group <= 1);
2935  switch (agr_group)
2936  {
2937  case 0:
2938  if (!bv)
2939  return arg_bv0.size();
2940  arg_bv0.push_back(bv);
2941  return arg_bv0.size();
2942  case 1:
2943  if (!bv)
2944  return arg_bv1.size();
2945  arg_bv1.push_back(bv);
2946  return arg_bv1.size();
2947  default:
2948  BM_ASSERT(0);
2949  }
2950  return 0;
2951 }
2952 
2953 // ------------------------------------------------------------------------
2954 
2955 
2956 } // bm
2957 
2958 
2959 #endif
ncbi::TMaskedQueryRegions mask
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
Algorithms for bvector<>
Definitions(internal)
#define BMRESTRICT
Definition: bmdef.h:203
#define BMNOEXCEPT
Definition: bmdef.h:82
#define BMGAP_PTR(ptr)
Definition: bmdef.h:189
#define BM_IS_GAP(ptr)
Definition: bmdef.h:191
#define BM_ASSERT
Definition: bmdef.h:139
#define BM_ASSERT_THROW(x, xerrcode)
Definition: bmdef.h:338
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:158
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:157
Bit manipulation primitives (internal)
#define false
Definition: bool.h:36
#define bool
Definition: bool.h:34
Pipeline vector for running a group of aggregation operations on a family of vectors.
Definition: bmaggregator.h:224
const bv_vector_type & get_all_input_vect() const noexcept
Definition: bmaggregator.h:295
bool is_complete_
ready to run state flag
Definition: bmaggregator.h:330
size_t compute_run_batch() const noexcept
Function looks at the pipeline to apply euristics to suggest optimal run_batch parameter.
run_options & options() noexcept
Set pipeline run options.
Definition: bmaggregator.h:232
void complete_arg_sub_group(index_vector_type &idx_vect, const bvector_type_const_ptr *bv_src, size_t size)
size_t total_vect_
total number of vector mentions in all groups
Definition: bmaggregator.h:331
const count_vector_type & get_all_input_cnt_vect() const noexcept
Definition: bmaggregator.h:297
bv_count_vector_type & get_bv_count_vector() noexcept
Return results vector count used for pipeline execution.
Definition: bmaggregator.h:287
const run_options & get_options() const noexcept
Get pipeline run options.
Definition: bmaggregator.h:235
bool is_complete() const noexcept
return true if pipeline is ready for execution (complete)
Definition: bmaggregator.h:269
void set_search_count_limit(size_type limit) noexcept
Set search limit for results.
Definition: bmaggregator.h:260
void set_or_target(bvector_type *bv_or) noexcept
Attach OR (aggregator vector).
Definition: bmaggregator.h:251
void complete_arg_group(arg_groups *ag)
size_type size() const noexcept
Return size() of pileine.
Definition: bmaggregator.h:272
bvector_type * bv_or_target_
OR target bit-bector ptr.
Definition: bmaggregator.h:340
unsigned top_blocks_
top-level structure size, max of all bvectors
Definition: bmaggregator.h:339
const arg_vector_type & get_args_vector() const noexcept
Return argument vector used for pipeline execution.
Definition: bmaggregator.h:279
bv_count_vector_type count_res_vect_
results (counts)
Definition: bmaggregator.h:335
arg_groups * add()
Add new arguments group.
size_type search_count_limit_
search limit by count
Definition: bmaggregator.h:336
pipeline(const pipeline &)=delete
pipeline & operator=(const pipeline &)=delete
pipeline_bcache & get_bcache() noexcept
Definition: bmaggregator.h:310
void complete()
Prepare pipeline for the execution (resize and init internal structures) Once complete,...
pipeline_bcache bcache_
blocks cache structure
Definition: bmaggregator.h:338
arg_vector_type arg_vect_
input arg. groups
Definition: bmaggregator.h:332
run_options options_
execution parameters
Definition: bmaggregator.h:329
unsigned get_top_blocks() const noexcept
Return number of top blocks after complete.
Definition: bmaggregator.h:315
bvect_vector_type bv_res_vect_
results (bit-vector ptrs)
Definition: bmaggregator.h:334
size_t unique_vectors() const noexcept
Return number of unique vectors in the pipeline (after complete())
Definition: bmaggregator.h:301
bvect_vector_type & get_bv_res_vector() noexcept
Return results vector used for pipeline execution.
Definition: bmaggregator.h:283
Algorithms for fast aggregation of a group of bit-vectors.
Definition: bmaggregator.h:122
BV::block_idx_type block_idx_type
Definition: bmaggregator.h:639
void combine_or(unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
bm::word_t * cache_gap_block(const bm::word_t *arg_blk, const size_t *src_idx, size_t k, unsigned i, unsigned j)
bvector_type * check_create_target()
unsigned top_block_size_
operation top block (i) size
Definition: bmaggregator.h:833
bool compute_count_
compute search result count
Definition: bmaggregator.h:849
bool test_gap_blocks_sub(size_t block_count, unsigned bit_idx)
arg_groups * arg_groups_type_ptr
Definition: bmaggregator.h:181
digest_type process_bit_blocks_sub(const arena &ar, digest_type digest)
pipeline_bcache * bcache_ptr_
Definition: bmaggregator.h:834
bm::heap_vector< bm::pair< unsigned, unsigned >, allocator_type, true > block_ij_vector_type
Definition: bmaggregator.h:191
void combine_and(unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
void combine_or(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
Aggregate group of vectors using logical OR.
int operation_
operation code (default: not defined)
Definition: bmaggregator.h:830
static const bm::word_t * get_arg_block(const bvector_type_const_ptr *bv_src, unsigned k, unsigned i, unsigned j) noexcept
allocator_pool_type pool_
pool for operations with cyclic mem.use
Definition: bmaggregator.h:827
arg_groups ag_
aggregator argument groups
Definition: bmaggregator.h:824
bm::word_t * temp_blk_
external temp block ptr
Definition: bmaggregator.h:829
bm::word_t * sort_input_blocks_and(const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
bm::heap_vector< bvector_type *, allocator_type, true > bvect_vector_type
Definition: bmaggregator.h:134
bm::heap_vector< bvector_type_const_ptr, allocator_type, true > bv_vector_type
Definition: bmaggregator.h:132
void combine_shift_right_and(bvector_type &bv_target)
Aggregate added group of vectors using SHIFT-RIGHT and logical AND Operation does NOT perform an expl...
bvector_type * bv_target_
target bit-vector
Definition: bmaggregator.h:832
bm::heap_vector< size_type, allocator_type, true > bv_count_vector_type
Definition: bmaggregator.h:187
static unsigned process_shift_right_and(bm::word_t *blk, const bm::word_t *arg_blk, digest_type &digest, unsigned carry_over) noexcept
BV::allocator_type allocator_type
Definition: bmaggregator.h:126
bool is_single_bit_
single bit flag
Definition: bmaggregator.h:843
bm::gap_word_t range_gap_blk_[5]
temp GAP range block
Definition: bmaggregator.h:840
static void free_arg_group(arg_groups *arg)
Definition: bmaggregator.h:802
operation_status run_step(unsigned i, unsigned j)
Run a step of current arrgegation operation.
static bool any_carry_overs(const unsigned char *carry_overs, size_t co_size) noexcept
void combine_and_sub(TPipe &pipe)
Run AND-SUB: AND (groups1) AND NOT ( OR(group0)) for a pipeline.
void stage(bm::word_t *temp_block)
Prepare operation, create internal resources, analyse dependencies.
bool combine_and_sub(bvector_type &bv_target)
Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit r...
bm::heap_vector< size_t, allocator_type, true > index_vector_type
Definition: bmaggregator.h:136
bm::id64_t digest_type
Definition: bmaggregator.h:128
void reset()
Reset aggregate groups, forget all attached vectors.
Definition: bmaggregator.h:941
void set_operation(int op_code) noexcept
Set operation code for the aggregator.
Definition: bmaggregator.h:609
bvector_type::blocks_manager_type blocks_manager_type
Definition: bmaggregator.h:638
arena * ar_
data arena ptr
Definition: bmaggregator.h:826
digest_type combine_and_sub(unsigned i, unsigned j, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, const bvector_type_const_ptr *bv_src_sub, size_t src_sub_size, int *is_result_full, bool find_all)
void combine_or(bvector_type &bv_target)
Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg...
bm::heap_vector< unsigned, allocator_type, true > count_vector_type
Definition: bmaggregator.h:185
digest_type process_bit_blocks_and(const arena &ar, digest_type digest, bool find_all)
BV::size_type size_type
Definition: bmaggregator.h:125
bool combine_and_sub(bvector_type &bv_target, bool any)
Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit r...
void combine_and(bvector_type &bv_target)
Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of ar...
digest_type process_gap_blocks_sub(const arena &ar, digest_type digest)
bm::heap_vector< const bm::word_t *, allocator_type, true > block_ptr_vector_type
Definition: bmaggregator.h:641
size_type range_from_
search from
Definition: bmaggregator.h:838
bool combine_shift_right_and(bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, bool any)
Fusion aggregate group of vectors using SHIFT right with AND.
static arg_groups * construct_arg_group()
Definition: bmaggregator.h:796
const bvector_type * bvector_type_const_ptr
Definition: bmaggregator.h:127
const bvector_type * get_target() const noexcept
Definition: bmaggregator.h:624
static unsigned find_effective_sub_block_size(unsigned i, const bvector_type_const_ptr *bv_src1, size_t src_size1, const bvector_type_const_ptr *bv_src2, size_t src_size2) noexcept
int get_operation() const noexcept
Get current operation code.
Definition: bmaggregator.h:606
bool find_first_and_sub(size_type &idx)
Aggregate added group of vectors using fused logical AND-SUB, find the first match.
bm::id64_t get_cache_gap_hits() const noexcept
Definition: bmaggregator.h:634
size_t add(const bvector_type *bv, unsigned agr_group=0)
Attach source bit-vector to a argument group (0 or 1).
bool combine_shift_right_and(unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
void reset_range_hint() noexcept
Reset range hint to false.
Definition: bmaggregator.h:962
operation
Codes for aggregation operations which can be pipelined for efficient execution.
Definition: bmaggregator.h:142
unsigned single_bit_idx_
Definition: bmaggregator.h:844
bm::word_t * sort_input_blocks_or(const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
bm::heap_vector< unsigned char, allocator_type, true > uchar_vector_type
Definition: bmaggregator.h:645
bm::word_t * get_temp_block() noexcept
Definition: bmaggregator.h:626
bool combine_and_sub(BII bi, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, const bvector_type_const_ptr *bv_src_sub, size_t src_sub_size)
void combine_and_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
Horizontal AND aggregation (potentially slower) method.
bm::heap_vector< bm::word_t *, allocator_type, true > blockptr_vector_type
Definition: bmaggregator.h:189
digest_type process_gap_blocks_and(const arena &ar, digest_type digest)
static unsigned find_effective_sub_block_size(unsigned i, const bvector_type_const_ptr *bv_src, size_t src_size, bool top_null_as_zero) noexcept
bool test_gap_blocks_and(size_t block_count, unsigned bit_idx)
void set_optimization(typename bvector_type::optmode opt=bvector_type::opt_compress) noexcept
set on-the-fly bit-block compression By default aggregator does not try to optimize result,...
Definition: bmaggregator.h:359
bool range_set_
pipeline blocks cache ptr
Definition: bmaggregator.h:837
size_type range_to_
search to
Definition: bmaggregator.h:839
size_type count() const
Definition: bmaggregator.h:488
bool combine_and_sub_bi(BII bi)
Aggregate added group of vectors using fused logical AND-SUB.
bool find_first_and_sub(size_type &idx, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, const bvector_type_const_ptr *bv_src_sub, size_t src_sub_size)
void prepare_shift_right_and(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
void process_gap_blocks_or(const arena &ar)
void set_compute_count(bool count_mode) noexcept
Definition: bmaggregator.h:363
tb_arena * tb_ar_
data arena ptr (heap allocated)
Definition: bmaggregator.h:825
static unsigned resize_target(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size, bool init_clear=true)
size_type count_
search result count
Definition: bmaggregator.h:850
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmaggregator.h:130
static arena * construct_arena()
Definition: bmaggregator.h:784
bm::heap_vector< arg_groups_type_ptr, allocator_type, true > arg_vector_type
Definition: bmaggregator.h:183
static unsigned max_top_blocks(const bvector_type_const_ptr *bv_src, size_t src_size) noexcept
bool combine_and_sub(bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, const bvector_type_const_ptr *bv_src_sub, size_t src_sub_size, bool any)
Fusion aggregate group of vectors using logical AND MINUS another set.
bm::heap_vector< const bm::gap_word_t *, allocator_type, true > gap_block_ptr_vector_type
Definition: bmaggregator.h:643
void combine_or_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
Horizontal OR aggregation (potentially slower) method.
operation_status operation_status_
Definition: bmaggregator.h:831
static void free_arena(arena *ar) noexcept
Definition: bmaggregator.h:789
void combine_and_sub_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, const bvector_type_const_ptr *bv_src_sub, size_t src_sub_size)
Horizontal AND-SUB aggregation (potentially slower) method.
bm::id64_t gap_cache_cnt_
Definition: bmaggregator.h:853
void combine_and(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
Aggregate group of vectors using logical AND.
bool set_range_hint(size_type from, size_type to) noexcept
Set search hint for the range, where results needs to be searched (experimental for internal use).
Definition: bmaggregator.h:974
bvector_type::optmode opt_mode_
perform search result optimization
Definition: bmaggregator.h:848
operation_status get_operation_status() const
Definition: bmaggregator.h:622
bool process_bit_blocks_or(blocks_manager_type &bman_target, unsigned i, unsigned j, const arena &ar)
value_type * data() const noexcept
Definition: bmbuffer.h:381
void resize(size_type new_size)
vector resize
Definition: bmbuffer.h:462
size_type size() const noexcept
Definition: bmbuffer.h:421
void reset() noexcept
Quick resize to zero.
Definition: bmbuffer.h:448
void push_back(const value_type &v)
push new element to the back of the vector
Definition: bmbuffer.h:534
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:51
bm::id_t bit_block_count(const bm::word_t *block) noexcept
Bitcount for bit block.
Definition: bmfunc.h:5051
bool bit_find_first(const bm::word_t *block, unsigned *pos) noexcept
BIT block find the first set bit.
Definition: bmfunc.h:8742
bm::id64_t bit_block_and_3way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bit-block AND
Definition: bmfunc.h:7011
bm::id64_t digest_mask(unsigned from, unsigned to) noexcept
Compute digest mask for [from..to] positions.
Definition: bmfunc.h:1025
unsigned word_bitcount64(bm::id64_t x) noexcept
Definition: bmutil.h:605
int for_each_bit_blk(const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a visitor functor for each 1 bit group
Definition: bmalgo_impl.h:1597
bool bit_block_or(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
Definition: bmfunc.h:7835
bm::id64_t bit_block_and(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:6858
void block_init_digest0(bm::word_t *const block, bm::id64_t digest) noexcept
Init block with 000111000 pattren based on digest.
Definition: bmfunc.h:1092
bool bit_block_or_3way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2) noexcept
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of s...
Definition: bmfunc.h:7952
bool is_bits_one(const bm::wordop_t *start) noexcept
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:6081
bool bit_is_all_zero(const bm::word_t *start) noexcept
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:1550
void bit_block_set(bm::word_t *dst, bm::word_t value) noexcept
Bitblock memset operation.
Definition: bmfunc.h:4456
bool bit_block_or_5way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, const bm::word_t *src3, const bm::word_t *src4) noexcept
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of sou...
Definition: bmfunc.h:7996
void bit_block_copy(bm::word_t *dst, const bm::word_t *src) noexcept
Bitblock copy operation.
Definition: bmfunc.h:6777
bm::id64_t bit_block_and_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bit-block AND
Definition: bmfunc.h:7076
bool bit_block_shift_r1_and_unr(bm::word_t *block, bm::word_t co_flag, const bm::word_t *mask_block, bm::id64_t *digest) noexcept
Right bit-shift bitblock by 1 bit (reference) + AND.
Definition: bmfunc.h:5962
bm::id64_t bit_block_sub_3way(bm::word_t *dst, const bm::word_t *src0, const bm::word_t *src1, bm::id64_t digest) noexcept
digest based bit-block SUB 3-way
Definition: bmfunc.h:8316
bool bit_find_first_if_1(const bm::word_t *block, unsigned *first, bm::id64_t digest) noexcept
BIT block find the first set bit if only 1 bit is set.
Definition: bmfunc.h:8838
bm::id64_t bit_block_sub_5way(bm::word_t *dst, const bm::word_t *src0, const bm::word_t *src1, const bm::word_t *src2, const bm::word_t *src3, bm::id64_t digest) noexcept
digest based bit-block SUB 5-way
Definition: bmfunc.h:8259
bm::id64_t bit_block_init_and_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bit-block AND (0 elements of digest will be zeroed)
Definition: bmfunc.h:7140
bm::id64_t calc_block_digest0(const bm::word_t *const block) noexcept
Compute digest for 64 non-zero areas.
Definition: bmfunc.h:1120
bm::id64_t bit_block_and_5way(bm::word_t *dst, const bm::word_t *src0, const bm::word_t *src1, const bm::word_t *src2, const bm::word_t *src3, bm::id64_t digest) noexcept
digest based bit-block AND 5-way
Definition: bmfunc.h:6949
bm::id64_t bit_block_sub(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
Definition: bmfunc.h:8105
@ READWRITE
mutable (read-write object)
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:148
void gap_add_to_bitset(unsigned *dest, const T *pcurr, unsigned len) noexcept
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:4039
unsigned gap_test_unr(const T *buf, const unsigned pos) noexcept
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1833
void gap_convert_to_bitset(unsigned *dest, const T *buf, unsigned len=0) noexcept
GAP block to bitblock conversion.
Definition: bmfunc.h:4475
void gap_and_to_bitset(unsigned *dest, const T *pcurr) noexcept
ANDs GAP block to bitblock.
Definition: bmfunc.h:4090
void gap_sub_to_bitset(unsigned *dest, const T *pcurr) noexcept
SUB (AND NOT) GAP block to bitblock.
Definition: bmfunc.h:3912
bm::agg_run_options< agg_disable_result_bvectors, agg_disable_counts > agg_opt_disable_bvects_and_counts
Pre-defined aggregator options to disable both intermediate results and counts.
Definition: bmaggregator.h:86
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1365
const bool agg_disable_search_masks
Definition: bmaggregator.h:55
const bool agg_produce_result_bvectors
Definition: bmaggregator.h:51
bm::agg_run_options< agg_disable_result_bvectors, agg_compute_counts > agg_opt_only_counts
Pre-defined aggregator options for counts-only (results dropped) operation.
Definition: bmaggregator.h:95
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1080
void aggregator_pipeline_execute(It first, It last)
Experimental method ro run multiple aggregators in sync.
Definition: bmaggregator.h:874
const bool agg_disable_counts
Definition: bmaggregator.h:54
bm::agg_run_options< agg_produce_result_bvectors, agg_compute_counts > agg_opt_bvect_and_counts
Pre-defined aggregator options for results plus counts operation.
Definition: bmaggregator.h:103
const bool agg_disable_result_bvectors
Definition: bmaggregator.h:52
const bool agg_compute_counts
Definition: bmaggregator.h:53
int i
int len
#include<zmmintrin.h>
Definition: bm.h:78
const unsigned set_array_mask
Definition: bmconst.h:97
const unsigned id_max
Definition: bmconst.h:109
unsigned int word_t
Definition: bmconst.h:39
const unsigned set_block_mask
Definition: bmconst.h:57
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition: bmalloc.h:464
const unsigned set_sub_array_size
Definition: bmconst.h:95
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) noexcept
Recalc linear bvector block index into 2D matrix coordinates.
Definition: bmfunc.h:180
bm::id_t block_to_global_index(unsigned i, unsigned j, unsigned block_idx) noexcept
calculate bvector<> global bit-index from block-local coords
Definition: bmfunc.h:10054
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:436
word_t wordop_t
Definition: bmconst.h:135
bool find_ptr(const void *const *p_arr, size_t arr_size, const void *ptr, size_t *idx) noexcept
Scan search for pointer value in unordered array.
Definition: bmfunc.h:10025
const unsigned set_word_shift
Definition: bmconst.h:72
const unsigned set_block_size
Definition: bmconst.h:55
unsigned long long int id64_t
Definition: bmconst.h:35
const unsigned set_array_shift
Definition: bmconst.h:96
unsigned short gap_word_t
Definition: bmconst.h:78
const unsigned gap_max_bits
Definition: bmconst.h:81
const unsigned set_top_array_size
Definition: bmconst.h:110
const unsigned set_block_shift
Definition: bmconst.h:56
const unsigned set_word_mask
Definition: bmconst.h:73
const unsigned bits_in_block
Definition: bmconst.h:114
const struct ncbi::grid::netcache::search::fields::SIZE size
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
static unsigned cnt[256]
Aggregation options to control execution Default settings are to support only result bit-vector filte...
Definition: bmaggregator.h:66
static constexpr bool is_make_results() noexcept
make result(target) vectors (aggregation search results) (Default: true) when false is used - means w...
Definition: bmaggregator.h:69
static constexpr bool is_compute_counts() noexcept
Compute counts for the target vectors, when set to true, population count is computed for each result...
Definition: bmaggregator.h:73
static constexpr bool is_masks() noexcept
Support for masking operations (Default: false)
Definition: bmaggregator.h:77
Temporary operations vectors.
Definition: bmaggregator.h:688
gap_block_ptr_vector_type v_arg_and_blk_gap
source GAP blocks list (AND)
Definition: bmaggregator.h:693
block_ptr_vector_type v_arg_and_blk
source blocks list (AND)
Definition: bmaggregator.h:692
block_ptr_vector_type v_arg_or_blk
source blocks list (OR)
Definition: bmaggregator.h:690
gap_block_ptr_vector_type v_arg_or_blk_gap
source GAP blocks list (OR)
Definition: bmaggregator.h:691
block_ptr_vector_type v_arg_tmp_blk
source blocks list
Definition: bmaggregator.h:689
uchar_vector_type carry_overs
shift carry over flags
Definition: bmaggregator.h:694
Aggregator arg groups.
Definition: bmaggregator.h:157
size_t add(const bvector_type *bv, unsigned agr_group)
Add bit-vector pointer to its aggregation group.
bv_vector_type arg_bv0
arg group 0
Definition: bmaggregator.h:158
bv_vector_type arg_bv1
arg group 1
Definition: bmaggregator.h:159
void reset()
Reset argument groups to zero.
Definition: bmaggregator.h:164
index_vector_type arg_idx0
indexes of vectors for arg group 0
Definition: bmaggregator.h:160
index_vector_type arg_idx1
Definition: bmaggregator.h:161
Block cache for pipeline execution.
Definition: bmaggregator.h:198
blockptr_vector_type blk_vect_
cached block ptrs for bv_inp_vect_
Definition: bmaggregator.h:201
count_vector_type cnt_vect_
usage count for bv_inp (all groups)
Definition: bmaggregator.h:200
bv_vector_type bv_inp_vect_
all input vectors from all groups
Definition: bmaggregator.h:199
block_ij_vector_type blk_ij_vect_
current block coords
Definition: bmaggregator.h:202
Aggregation options for runtime control.
Definition: bmaggregator.h:209
size_t batch_size
Batch size sets number of argument groups processed at a time Default: 0 means this parameter will be...
Definition: bmaggregator.h:212
Alllocated blocka of scratch memory.
Definition: bmaggregator.h:814
bm::bit_block_t tb_opt
temp block for results optimization
Definition: bmaggregator.h:816
functor-adaptor for back-inserter
Definition: bmalgo_impl.h:159
Pair type.
Definition: bmfunc.h:154
Second second
Definition: bmfunc.h:156
First first
Definition: bmfunc.h:155
#define const
Definition: zconf.h:230
Modified on Wed Feb 21 09:57:49 2024 by modify_doxy.py rev. 669887