nicola.cabiddu_1772

Committed 31 May 2024 12:58PM UTC coverage: 90.685%. First build

Build # nicola.cabiddu_1772

Build Type

Pull #7668

Evergreen

Committed by

jedelbo

Commit Message

Update tests

Pull Request Pull Request #7668: RCORE-2094 Compressing Integer Arrays

Run Details

102170 of 180138 branches covered (56.72%)

1749 of 1914 new or added lines in 36 files covered. (91.38%)

217024 of 239317 relevant lines covered (90.68%)

6624441.54 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.35

/src/realm/integer_packed_compressor.hpp

/*************************************************************************
 *
 * Copyright 2024 Realm Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************/

#ifndef PACKED_COMPRESSOR_HPP
#define PACKED_COMPRESSOR_HPP

#include <realm/array.hpp>
#include <realm/array_direct.hpp>

#include <cstdint>
#include <stddef.h>

namespace realm {

//
// Compress array in Packed format
// Decompress array in WTypeBits formats
//
class PackedCompressor {
public:
    // encoding/decoding
    static void init_header(char*, uint8_t, uint8_t, size_t);
    static void copy_data(const Array&, Array&);
    // get or set
    static int64_t get(const IntegerCompressor&, size_t);
    static std::vector<int64_t> get_all(const IntegerCompressor& c, size_t b, size_t e);
    static void get_chunk(const IntegerCompressor&, size_t, int64_t res[8]);
    static void set_direct(const IntegerCompressor&, size_t, int64_t);

    template <typename Cond>
    static bool find_all(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);

private:
    static bool find_all_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state);

    template <typename VectorCond>
    static bool find_parallel(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);

    template <typename Cond>
    static bool find_linear(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);

    template <typename Cond>
    static bool run_parallel_scan(size_t, size_t);
};

inline int64_t PackedCompressor::get(const IntegerCompressor& c, size_t ndx)
{
    BfIterator it{c.data(), 0, c.v_width(), c.v_width(), ndx};
    return sign_extend_field_by_mask(c.v_mask(), *it);
}

inline std::vector<int64_t> PackedCompressor::get_all(const IntegerCompressor& c, size_t b, size_t e)
{
    const auto range = (e - b);
    const auto v_w = c.v_width();
    const auto data = c.data();
    const auto sign_mask = c.v_mask();
    const auto starting_bit = b * v_w;
    const auto total_bits = starting_bit + (v_w * range);
    const auto mask = 0xFFFFFFFFFFFFFFFFULL >> (64 - v_w);
    const auto bit_per_it = num_bits_for_width(v_w);
    const auto values_per_word = num_fields_for_width(v_w);

    std::vector<int64_t> res;
    res.reserve(range);

    UnalignedWordIter unaligned_data_iterator(data, starting_bit);
    auto cnt_bits = starting_bit;
    while (cnt_bits + bit_per_it < total_bits) {
        auto word = unaligned_data_iterator.consume(bit_per_it);
        for (int i = 0; i < values_per_word; ++i) {
            res.push_back(sign_extend_field_by_mask(sign_mask, word & mask));
            word >>= v_w;
        }
        cnt_bits += bit_per_it;
    }
    if (cnt_bits < total_bits) {
        auto last_word = unaligned_data_iterator.consume(static_cast<unsigned>(total_bits - cnt_bits));
        while (cnt_bits < total_bits) {
            res.push_back(sign_extend_field_by_mask(sign_mask, last_word & mask));
            cnt_bits += v_w;
            last_word >>= v_w;
        }
    }
    return res;
}

inline void PackedCompressor::set_direct(const IntegerCompressor& c, size_t ndx, int64_t value)
{
    BfIterator it{c.data(), 0, c.v_width(), c.v_width(), ndx};
    it.set_value(value);
}

inline void PackedCompressor::get_chunk(const IntegerCompressor& c, size_t ndx, int64_t res[8])
{
    auto sz = 8;
    std::memset(res, 0, sizeof(int64_t) * sz);
    auto supposed_end = ndx + sz;
    size_t i = ndx;
    size_t index = 0;
    // this can be done better, in one go, retrieve both!!!
    for (; i < supposed_end; ++i) {
        res[index++] = get(c, i);
    }
    for (; index < 8; ++index) {
        res[index++] = get(c, i++);
    }
}


template <typename Cond>
inline bool PackedCompressor::find_all(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
                                       QueryStateBase* state)
{
    REALM_ASSERT_DEBUG(start <= arr.m_size && (end <= arr.m_size || end == size_t(-1)) && start <= end);
    Cond c;

    if (end == npos)
        end = arr.m_size;

    if (!(arr.m_size > start && start < end))
        return true;

    const auto lbound = arr.m_lbound;
    const auto ubound = arr.m_ubound;

    if (!c.can_match(value, lbound, ubound))
        return true;

    if (c.will_match(value, lbound, ubound)) {
        return find_all_match(start, end, baseindex, state);
    }

    REALM_ASSERT_DEBUG(arr.m_width != 0);

    if (!run_parallel_scan<Cond>(arr.m_width, end - start))
        return find_linear<Cond>(arr, value, start, end, baseindex, state);

    return find_parallel<Cond>(arr, value, start, end, baseindex, state);
}

template <typename VectorCond>
inline bool PackedCompressor::find_parallel(const Array& arr, int64_t value, size_t start, size_t end,
                                            size_t baseindex, QueryStateBase* state)
{
    //
    // Main idea around find parallel (applicable to flex arrays too).
    // Try to find the starting point where the condition can be met, comparing as many values as a single 64bit can
    // contain in parallel. Once we have found the starting point, keep matching values as much as we can between
    // start and end.
    //
    // EG: let's store 6, it gets stored in 4 bits (0110). 6 is 4 bits because 110 (6) + sign bit 0.
    // Inside 64bits we can fit max 16 times 6. If we go from index 0 to 15 throughout the same 64 bits, we need to
    // apply a mask and a shift bits every time, then compare the extracted values.
    // This is not the cheapest thing to do. Instead we can compare all values contained within 64 bits in one go, and
    // see if there is a match with what we are looking for. Reducing the number of comparison by ~logk(N) where K is
    // the width of each single value within a 64 bit word and N is the total number of values stored in the array.

    const auto data = (const uint64_t*)arr.m_data;
    const auto width = arr.m_width;
    const auto MSBs = arr.integer_compressor().msb();
    const auto search_vector = populate(arr.m_width, value);
    while (start < end) {
        start = parallel_subword_find(find_all_fields<VectorCond>, data, 0, width, MSBs, search_vector, start, end);
        if (start < end && !state->match(start + baseindex))
            return false;
        ++start;
    }
    return true;
}

template <typename Cond>
inline bool PackedCompressor::find_linear(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
                                          QueryStateBase* state)
{
    auto compare = [](int64_t a, int64_t b) {
        if constexpr (std::is_same_v<Cond, Equal>)
            return a == b;
        if constexpr (std::is_same_v<Cond, NotEqual>)
            return a != b;
        if constexpr (std::is_same_v<Cond, Greater>)
            return a > b;
        if constexpr (std::is_same_v<Cond, Less>)
            return a < b;
    };
    const auto& c = arr.integer_compressor();
    BfIterator it{c.data(), 0, c.v_width(), c.v_width(), start};
    for (; start < end; ++start) {
        it.move(start);
        const auto sv = sign_extend_field_by_mask(c.v_mask(), *it);
        if (compare(sv, value) && !state->match(start + baseindex))
            return false;
    }
    return true;
}

template <typename Cond>
inline bool PackedCompressor::run_parallel_scan(size_t width, size_t range)
{
    if constexpr (std::is_same_v<Cond, NotEqual>) {
        // we seem to be particularly slow doing parallel scan in packed for NotEqual.
        // we are much better with a linear scan. TODO: investigate this.
        return false;
    }
    if constexpr (std::is_same_v<Cond, Equal>) {
        return width < 32 && range >= 20;
    }
    // > and < need a different heuristic
    return width <= 20 && range >= 20;
}

} // namespace realm

#endif // PACKED_COMPRESSOR_HPP

1	/*************************************************************************
2	*
3	* Copyright 2024 Realm Inc.
4	*
5	* Licensed under the Apache License, Version 2.0 (the "License");
6	* you may not use this file except in compliance with the License.
7	* You may obtain a copy of the License at
8	*
9	* http://www.apache.org/licenses/LICENSE-2.0
10	*
11	* Unless required by applicable law or agreed to in writing, software
12	* distributed under the License is distributed on an "AS IS" BASIS,
13	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14	* See the License for the specific language governing permissions and
15	* limitations under the License.
16	*
17	**************************************************************************/
18
19	#ifndef PACKED_COMPRESSOR_HPP
20	#define PACKED_COMPRESSOR_HPP
21
22	#include <realm/array.hpp>
23	#include <realm/array_direct.hpp>
24
25	#include <cstdint>
26	#include <stddef.h>
27
28	namespace realm {
29
30	//
31	// Compress array in Packed format
32	// Decompress array in WTypeBits formats
33	//
34	class PackedCompressor {
35	public:
36	// encoding/decoding
37	static void init_header(char*, uint8_t, uint8_t, size_t);
38	static void copy_data(const Array&, Array&);
39	// get or set
40	static int64_t get(const IntegerCompressor&, size_t);
41	static std::vector<int64_t> get_all(const IntegerCompressor& c, size_t b, size_t e);
42	static void get_chunk(const IntegerCompressor&, size_t, int64_t res[8]);
43	static void set_direct(const IntegerCompressor&, size_t, int64_t);
44
45	template <typename Cond>
46	static bool find_all(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
47
48	private:
49	static bool find_all_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state);
50
51	template <typename VectorCond>
52	static bool find_parallel(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
53
54	template <typename Cond>
55	static bool find_linear(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
56
57	template <typename Cond>
58	static bool run_parallel_scan(size_t, size_t);
59	};
60
61	inline int64_t PackedCompressor::get(const IntegerCompressor& c, size_t ndx)
62	{	64,573,443✔
63	BfIterator it{c.data(), 0, c.v_width(), c.v_width(), ndx};	64,573,443✔
64	return sign_extend_field_by_mask(c.v_mask(), *it);	64,573,443✔
65	}	64,573,443✔
66
67	inline std::vector<int64_t> PackedCompressor::get_all(const IntegerCompressor& c, size_t b, size_t e)
68	{	6✔
69	const auto range = (e - b);	6✔
70	const auto v_w = c.v_width();	6✔
71	const auto data = c.data();	6✔
72	const auto sign_mask = c.v_mask();	6✔
73	const auto starting_bit = b * v_w;	6✔
74	const auto total_bits = starting_bit + (v_w * range);	6✔
75	const auto mask = 0xFFFFFFFFFFFFFFFFULL >> (64 - v_w);	6✔
76	const auto bit_per_it = num_bits_for_width(v_w);	6✔
77	const auto values_per_word = num_fields_for_width(v_w);	6✔
78
79	std::vector<int64_t> res;	6✔
80	res.reserve(range);	6✔
81
82	UnalignedWordIter unaligned_data_iterator(data, starting_bit);	6✔
83	auto cnt_bits = starting_bit;	6✔
84	while (cnt_bits + bit_per_it < total_bits) {	96✔
85	auto word = unaligned_data_iterator.consume(bit_per_it);	90✔
86	for (int i = 0; i < values_per_word; ++i) {	180✔
87	res.push_back(sign_extend_field_by_mask(sign_mask, word & mask));	90✔
88	word >>= v_w;	90✔
89	}	90✔
90	cnt_bits += bit_per_it;	90✔
91	}	90✔
92	if (cnt_bits < total_bits) {	6✔
93	auto last_word = unaligned_data_iterator.consume(static_cast<unsigned>(total_bits - cnt_bits));	6✔
94	while (cnt_bits < total_bits) {	12✔
95	res.push_back(sign_extend_field_by_mask(sign_mask, last_word & mask));	6✔
96	cnt_bits += v_w;	6✔
97	last_word >>= v_w;	6✔
98	}	6✔
99	}	6✔
100	return res;	6✔
101	}	6✔
102
103	inline void PackedCompressor::set_direct(const IntegerCompressor& c, size_t ndx, int64_t value)
NEW 104	{	×
NEW 105	BfIterator it{c.data(), 0, c.v_width(), c.v_width(), ndx};	×
NEW 106	it.set_value(value);	×
NEW 107	}	×
108
109	inline void PackedCompressor::get_chunk(const IntegerCompressor& c, size_t ndx, int64_t res[8])
NEW 110	{	×
NEW 111	auto sz = 8;	×
NEW 112	std::memset(res, 0, sizeof(int64_t) * sz);	×
NEW 113	auto supposed_end = ndx + sz;	×
NEW 114	size_t i = ndx;	×
NEW 115	size_t index = 0;	×
116	// this can be done better, in one go, retrieve both!!!
NEW 117	for (; i < supposed_end; ++i) {	×
NEW 118	res[index++] = get(c, i);	×
NEW 119	}	×
NEW 120	for (; index < 8; ++index) {	×
NEW 121	res[index++] = get(c, i++);	×
NEW 122	}	×
NEW 123	}	×
124
125
126	template <typename Cond>
127	inline bool PackedCompressor::find_all(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
128	QueryStateBase* state)
129	{	5,549,253✔
130	REALM_ASSERT_DEBUG(start <= arr.m_size && (end <= arr.m_size \|\| end == size_t(-1)) && start <= end);	5,549,253!
131	Cond c;	5,549,253✔
132
133	if (end == npos)	5,549,253✔
NEW 134	end = arr.m_size;	×
135
136	if (!(arr.m_size > start && start < end))	5,577,594✔
137	return true;	1,326✔
138
139	const auto lbound = arr.m_lbound;	5,547,927✔
140	const auto ubound = arr.m_ubound;	5,547,927✔
141
142	if (!c.can_match(value, lbound, ubound))	5,547,927✔
143	return true;	1,980,972✔
144
145	if (c.will_match(value, lbound, ubound)) {	3,566,955✔
146	return find_all_match(start, end, baseindex, state);	23,256✔
147	}	23,256✔
148
149	REALM_ASSERT_DEBUG(arr.m_width != 0);	3,543,699✔
150
151	if (!run_parallel_scan<Cond>(arr.m_width, end - start))	3,543,699✔
152	return find_linear<Cond>(arr, value, start, end, baseindex, state);	34,368✔
153
154	return find_parallel<Cond>(arr, value, start, end, baseindex, state);	3,509,331✔
155	}	3,543,699✔
156
157	template <typename VectorCond>
158	inline bool PackedCompressor::find_parallel(const Array& arr, int64_t value, size_t start, size_t end,
159	size_t baseindex, QueryStateBase* state)
160	{	3,369,030✔
161	//
162	// Main idea around find parallel (applicable to flex arrays too).
163	// Try to find the starting point where the condition can be met, comparing as many values as a single 64bit can
164	// contain in parallel. Once we have found the starting point, keep matching values as much as we can between
165	// start and end.
166	//
167	// EG: let's store 6, it gets stored in 4 bits (0110). 6 is 4 bits because 110 (6) + sign bit 0.
168	// Inside 64bits we can fit max 16 times 6. If we go from index 0 to 15 throughout the same 64 bits, we need to
169	// apply a mask and a shift bits every time, then compare the extracted values.
170	// This is not the cheapest thing to do. Instead we can compare all values contained within 64 bits in one go, and
171	// see if there is a match with what we are looking for. Reducing the number of comparison by ~logk(N) where K is
172	// the width of each single value within a 64 bit word and N is the total number of values stored in the array.
173
174	const auto data = (const uint64_t*)arr.m_data;	3,369,030✔
175	const auto width = arr.m_width;	3,369,030✔
176	const auto MSBs = arr.integer_compressor().msb();	3,369,030✔
177	const auto search_vector = populate(arr.m_width, value);	3,369,030✔
178	while (start < end) {	14,327,961✔
179	start = parallel_subword_find(find_all_fields<VectorCond>, data, 0, width, MSBs, search_vector, start, end);	10,980,873✔
180	if (start < end && !state->match(start + baseindex))	10,980,873✔
181	return false;	21,942✔
182	++start;	10,958,931✔
183	}	10,958,931✔
184	return true;	3,347,088✔
185	}	3,369,030✔
186
187	template <typename Cond>
188	inline bool PackedCompressor::find_linear(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
189	QueryStateBase* state)
190	{	34,368✔
191	auto compare = [](int64_t a, int64_t b) {	6,054,765✔
192	if constexpr (std::is_same_v<Cond, Equal>)	3,051,765✔
193	return a == b;	216✔
194	if constexpr (std::is_same_v<Cond, NotEqual>)	3,051,684✔
195	return a != b;	6,031,062✔
196	if constexpr (std::is_same_v<Cond, Greater>)	11,751✔
197	return a > b;	13,344✔
198	if constexpr (std::is_same_v<Cond, Less>)	5,091✔
199	return a < b;	10,104✔
200	};	3,003,000✔
201	const auto& c = arr.integer_compressor();	34,368✔
202	BfIterator it{c.data(), 0, c.v_width(), c.v_width(), start};	34,368✔
203	for (; start < end; ++start) {	6,065,835✔
204	it.move(start);	6,051,795✔
205	const auto sv = sign_extend_field_by_mask(c.v_mask(), *it);	6,051,795✔
206	if (compare(sv, value) && !state->match(start + baseindex))	6,053,268✔
207	return false;	20,328✔
208	}	6,051,795✔
209	return true;	14,040✔
210	}	34,368✔
211
212	template <typename Cond>
213	inline bool PackedCompressor::run_parallel_scan(size_t width, size_t range)
214	{	3,963,819✔
215	if constexpr (std::is_same_v<Cond, NotEqual>) {	3,963,819✔
216	// we seem to be particularly slow doing parallel scan in packed for NotEqual.
217	// we are much better with a linear scan. TODO: investigate this.
218	return false;	11,676✔
219	}	11,676✔
220	if constexpr (std::is_same_v<Cond, Equal>) {	3,924,429✔
221	return width < 32 && range >= 20;	3,901,989✔
222	}	3,896,448✔
223	// > and < need a different heuristic
224	return width <= 20 && range >= 20;	2,035,626!
225	}	3,963,819✔
226
227	} // namespace realm
228
229	#endif // PACKED_COMPRESSOR_HPP

realm / realm-core / nicola.cabiddu_1772

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous