jorgen.edelbo_389

Committed 12 Aug 2024 02:13PM UTC coverage: 91.085% (-0.02%) from 91.107%

Build # jorgen.edelbo_389

Build Type

Pull #7826

Evergreen

Committed by

jedelbo

Commit Message

Bump file format version

Pull Request Pull Request #7826: Merge Next major

Run Details

103458 of 182206 branches covered (56.78%)

3138 of 3500 new or added lines in 53 files covered. (89.66%)

175 existing lines in 17 files now uncovered.

219944 of 241471 relevant lines covered (91.09%)

6840929.52 hits per line

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

86.52

/src/realm/integer_flex_compressor.hpp

/*************************************************************************
 *
 * Copyright 2023 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 FLEX_COMPRESSOR_HPP
#define FLEX_COMPRESSOR_HPP

#include <realm/array.hpp>

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

namespace realm {

//
// Compress array in Flex format
// Decompress array in WTypeBits formats
//
class FlexCompressor {
public:
    // encoding/decoding
    static void init_header(char*, uint8_t, uint8_t, uint8_t, size_t, size_t);
    static void copy_data(const Array&, const std::vector<int64_t>&, const std::vector<unsigned>&);
    // getters/setters
    static int64_t get(const IntegerCompressor&, size_t);
    static std::vector<int64_t> get_all(const IntegerCompressor&, size_t, size_t);
    static void get_chunk(const IntegerCompressor&, size_t, int64_t[8]);

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

    static int64_t min(const IntegerCompressor&);
    static int64_t max(const IntegerCompressor&);

private:
    static bool find_all_match(size_t, size_t, size_t, QueryStateBase*);
    static size_t lower_bound(size_t, int64_t, uint64_t, BfIterator&) noexcept;
};

inline int64_t FlexCompressor::get(const IntegerCompressor& c, size_t ndx)
{
    const auto offset = c.v_width() * c.v_size();
    const auto ndx_w = c.ndx_width();
    const auto v_w = c.v_width();
    const auto data = c.data();
    BfIterator ndx_iterator{data, offset, ndx_w, ndx_w, ndx};
    BfIterator data_iterator{data, 0, v_w, v_w, static_cast<size_t>(*ndx_iterator)};
    return sign_extend_field_by_mask(c.v_mask(), *data_iterator);
}

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

    // this is very important, x4 faster pre-allocating the array
    std::vector<int64_t> res;
    res.reserve(range);

    UnalignedWordIter unaligned_ndx_iterator(data, starting_bit);
    BfIterator data_iterator{data, 0, v_w, v_w, 0};
    auto remaining_bits = ndx_w * range;
    while (remaining_bits >= bit_per_it) {
        auto word = unaligned_ndx_iterator.consume(bit_per_it);
        for (int i = 0; i < values_per_word; ++i) {
            const auto index = word & ndx_mask;
            data_iterator.move(static_cast<size_t>(index));
            const auto sv = sign_extend_field_by_mask(sign_mask, *data_iterator);
            res.push_back(sv);
            word >>= ndx_w;
        }
        remaining_bits -= bit_per_it;
    }
    if (remaining_bits) {
        auto last_word = unaligned_ndx_iterator.consume(remaining_bits);
        while (remaining_bits) {
            const auto index = last_word & ndx_mask;
            data_iterator.move(static_cast<size_t>(index));
            const auto sv = sign_extend_field_by_mask(sign_mask, *data_iterator);
            res.push_back(sv);
            remaining_bits -= ndx_w;
            last_word >>= ndx_w;
        }
    }
    return res;
}

inline int64_t FlexCompressor::min(const IntegerCompressor& c)
{
    const auto v_w = c.v_width();
    const auto data = c.data();
    const auto sign_mask = c.v_mask();
    BfIterator data_iterator{data, 0, v_w, v_w, 0};
    return sign_extend_field_by_mask(sign_mask, *data_iterator);
}

inline int64_t FlexCompressor::max(const IntegerCompressor& c)
{
    const auto v_w = c.v_width();
    const auto data = c.data();
    const auto sign_mask = c.v_mask();
    BfIterator data_iterator{data, 0, v_w, v_w, c.v_size() - 1};
    return sign_extend_field_by_mask(sign_mask, *data_iterator);
}

inline void FlexCompressor::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;
    for (; i < supposed_end; ++i) {
        res[index++] = get(c, i);
    }
    for (; index < 8; ++index) {
        res[index++] = get(c, i++);
    }
}

template <typename T>
class IndexCond {
public:
    using type = T;
};

template <>
class IndexCond<Greater> {
public:
    using type = GreaterEqual;
};

template <typename Cond>
inline bool FlexCompressor::find_all(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
                                     QueryStateBase* state)
{
    static constexpr size_t RANGE_LIMIT = 20;
    static constexpr size_t WIDTH_LIMIT = 16;

    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 (start >= arr.m_size || 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);

    const auto& compressor = arr.integer_compressor();
    const auto v_width = arr.m_width;
    const auto v_size = compressor.v_size();
    const auto mask = compressor.v_mask();
    uint64_t* data = (uint64_t*)arr.m_data;
    size_t v_start = realm::not_found;

    /**************** Search the values ****************/

    int64_t modified_value = value;
    if constexpr (std::is_same_v<Cond, Greater>) {
        modified_value++; // We use GreaterEqual below, so this will effectively be Greater
    }

    if (v_size >= RANGE_LIMIT) {
        if (v_width <= WIDTH_LIMIT) {
            auto search_vector = populate(v_width, modified_value);
            v_start = parallel_subword_find(find_all_fields<GreaterEqual>, data, 0, v_width, compressor.msb(),
                                            search_vector, 0, v_size);
        }
        else {
            BfIterator data_iterator{data, 0, v_width, v_width, 0};
            v_start = lower_bound(v_size, modified_value, mask, data_iterator);
        }
    }
    else {
        BfIterator data_iterator{data, 0, v_width, v_width, 0};
        size_t idx = 0;
        while (idx < v_size) {
            if (sign_extend_field_by_mask(mask, *data_iterator) >= modified_value) {
                break;
            }
            data_iterator.move(++idx);
        }
        v_start = idx;
    }

    if constexpr (realm::is_any_v<Cond, Equal, NotEqual>) {
        // Check for equality.
        if (v_start < v_size) {
            BfIterator it{data, 0, v_width, v_width, v_start};
            if (sign_extend_field_by_mask(mask, *it) > value) {
                v_start = v_size; // Mark as not found
            }
        }
    }

    /***************** Some early outs *****************/

    if (v_start == v_size) {
        if constexpr (realm::is_any_v<Cond, Equal, Greater>) {
            return true; // No Matches
        }
        if constexpr (realm::is_any_v<Cond, NotEqual, Less>) {
            return find_all_match(start, end, baseindex, state); // All matches
        }
    }
    else if (v_start == 0) {
        if constexpr (std::is_same_v<Cond, Less>) {
            // No index is less than 0
            return true; // No Matches
        }
        if constexpr (std::is_same_v<Cond, Greater>) {
            // All index is greater than or equal to 0
            return find_all_match(start, end, baseindex, state);
        }
    }

    /*************** Search the indexes ****************/

    using U = typename IndexCond<Cond>::type;
    const auto ndx_range = end - start;
    const auto ndx_width = compressor.ndx_width();
    const auto v_offset = v_size * v_width;
    if (ndx_range >= RANGE_LIMIT) {
        auto search_vector = populate(ndx_width, v_start);
        while (start < end) {
            start = parallel_subword_find(find_all_fields_unsigned<U>, data, v_offset, ndx_width,
                                          compressor.ndx_msb(), search_vector, start, end);
            if (start < end) {
                if (!state->match(start + baseindex))
                    return false;
            }
            ++start;
        }
    }
    else {
        U index_c;
        BfIterator ndx_iterator{data, v_offset, ndx_width, ndx_width, start};
        while (start < end) {
            if (index_c(int64_t(*ndx_iterator), int64_t(v_start))) {
                if (!state->match(start + baseindex))
                    return false;
            }
            ndx_iterator.move(++start);
        }
    }

    return true;
}

} // namespace realm
#endif // FLEX_COMPRESSOR_HPP

1	/*************************************************************************
2	*
3	* Copyright 2023 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 FLEX_COMPRESSOR_HPP
20	#define FLEX_COMPRESSOR_HPP
21
22	#include <realm/array.hpp>
23
24	#include <cstdint>
25	#include <stddef.h>
26	#include <vector>
27
28	namespace realm {
29
30	//
31	// Compress array in Flex format
32	// Decompress array in WTypeBits formats
33	//
34	class FlexCompressor {
35	public:
36	// encoding/decoding
37	static void init_header(char*, uint8_t, uint8_t, uint8_t, size_t, size_t);
38	static void copy_data(const Array&, const std::vector<int64_t>&, const std::vector<unsigned>&);
39	// getters/setters
40	static int64_t get(const IntegerCompressor&, size_t);
41	static std::vector<int64_t> get_all(const IntegerCompressor&, size_t, size_t);
42	static void get_chunk(const IntegerCompressor&, size_t, int64_t[8]);
43
44	template <typename Cond>
45	static bool find_all(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
46
47	static int64_t min(const IntegerCompressor&);
48	static int64_t max(const IntegerCompressor&);
49
50	private:
51	static bool find_all_match(size_t, size_t, size_t, QueryStateBase*);
52	static size_t lower_bound(size_t, int64_t, uint64_t, BfIterator&) noexcept;
53	};
54
55	inline int64_t FlexCompressor::get(const IntegerCompressor& c, size_t ndx)
56	{	3,974,277✔
57	const auto offset = c.v_width() * c.v_size();	3,974,277✔
58	const auto ndx_w = c.ndx_width();	3,974,277✔
59	const auto v_w = c.v_width();	3,974,277✔
60	const auto data = c.data();	3,974,277✔
61	BfIterator ndx_iterator{data, offset, ndx_w, ndx_w, ndx};	3,974,277✔
62	BfIterator data_iterator{data, 0, v_w, v_w, static_cast<size_t>(*ndx_iterator)};	3,974,277✔
63	return sign_extend_field_by_mask(c.v_mask(), *data_iterator);	3,974,277✔
64	}	3,974,277✔
65
66	inline std::vector<int64_t> FlexCompressor::get_all(const IntegerCompressor& c, size_t b, size_t e)
67	{	31,056✔
68	const auto offset = c.v_width() * c.v_size();	31,056✔
69	const auto ndx_w = c.ndx_width();	31,056✔
70	const auto v_w = c.v_width();	31,056✔
71	const auto data = c.data();	31,056✔
72	const auto sign_mask = c.v_mask();	31,056✔
73	const auto range = (e - b);	31,056✔
74	const auto starting_bit = offset + b * ndx_w;	31,056✔
75	const auto bit_per_it = num_bits_for_width(ndx_w);	31,056✔
76	const auto ndx_mask = 0xFFFFFFFFFFFFFFFFULL >> (64 - ndx_w);	31,056✔
77	const auto values_per_word = num_fields_for_width(ndx_w);	31,056✔
78
79	// this is very important, x4 faster pre-allocating the array
80	std::vector<int64_t> res;	31,056✔
81	res.reserve(range);	31,056✔
82
83	UnalignedWordIter unaligned_ndx_iterator(data, starting_bit);	31,056✔
84	BfIterator data_iterator{data, 0, v_w, v_w, 0};	31,056✔
85	auto remaining_bits = ndx_w * range;	31,056✔
86	while (remaining_bits >= bit_per_it) {	382,914✔
87	auto word = unaligned_ndx_iterator.consume(bit_per_it);	351,858✔
88	for (int i = 0; i < values_per_word; ++i) {	3,888,813✔
89	const auto index = word & ndx_mask;	3,536,955✔
90	data_iterator.move(static_cast<size_t>(index));	3,536,955✔
91	const auto sv = sign_extend_field_by_mask(sign_mask, *data_iterator);	3,536,955✔
92	res.push_back(sv);	3,536,955✔
93	word >>= ndx_w;	3,536,955✔
94	}	3,536,955✔
95	remaining_bits -= bit_per_it;	351,858✔
96	}	351,858✔
97	if (remaining_bits) {	31,056✔
98	auto last_word = unaligned_ndx_iterator.consume(remaining_bits);	26,313✔
99	while (remaining_bits) {	217,266✔
100	const auto index = last_word & ndx_mask;	190,953✔
101	data_iterator.move(static_cast<size_t>(index));	190,953✔
102	const auto sv = sign_extend_field_by_mask(sign_mask, *data_iterator);	190,953✔
103	res.push_back(sv);	190,953✔
104	remaining_bits -= ndx_w;	190,953✔
105	last_word >>= ndx_w;	190,953✔
106	}	190,953✔
107	}	26,313✔
108	return res;	31,056✔
109	}	31,056✔
110
111	inline int64_t FlexCompressor::min(const IntegerCompressor& c)
112	{	31,056✔
113	const auto v_w = c.v_width();	31,056✔
114	const auto data = c.data();	31,056✔
115	const auto sign_mask = c.v_mask();	31,056✔
116	BfIterator data_iterator{data, 0, v_w, v_w, 0};	31,056✔
117	return sign_extend_field_by_mask(sign_mask, *data_iterator);	31,056✔
118	}	31,056✔
119
120	inline int64_t FlexCompressor::max(const IntegerCompressor& c)
121	{	31,056✔
122	const auto v_w = c.v_width();	31,056✔
123	const auto data = c.data();	31,056✔
124	const auto sign_mask = c.v_mask();	31,056✔
125	BfIterator data_iterator{data, 0, v_w, v_w, c.v_size() - 1};	31,056✔
126	return sign_extend_field_by_mask(sign_mask, *data_iterator);	31,056✔
127	}	31,056✔
128
129	inline void FlexCompressor::get_chunk(const IntegerCompressor& c, size_t ndx, int64_t res[8])
NEW 130	{	×
NEW 131	auto sz = 8;	×
NEW 132	std::memset(res, 0, sizeof(int64_t) * sz);	×
NEW 133	auto supposed_end = ndx + sz;	×
NEW 134	size_t i = ndx;	×
NEW 135	size_t index = 0;	×
NEW 136	for (; i < supposed_end; ++i) {	×
NEW 137	res[index++] = get(c, i);	×
NEW 138	}	×
NEW 139	for (; index < 8; ++index) {	×
NEW 140	res[index++] = get(c, i++);	×
NEW 141	}	×
NEW 142	}	×
143
144	template <typename T>
145	class IndexCond {
146	public:
147	using type = T;
148	};
149
150	template <>
151	class IndexCond<Greater> {
152	public:
153	using type = GreaterEqual;
154	};
155
156	template <typename Cond>
157	inline bool FlexCompressor::find_all(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
158	QueryStateBase* state)
159	{	912✔
160	static constexpr size_t RANGE_LIMIT = 20;	912✔
161	static constexpr size_t WIDTH_LIMIT = 16;	912✔
162
163	REALM_ASSERT_DEBUG(start <= arr.m_size && (end <= arr.m_size \|\| end == size_t(-1)) && start <= end);	912!
164	Cond c;	912✔
165
166	if (end == npos)	912✔
NEW 167	end = arr.m_size;	×
168
169	if (start >= arr.m_size \|\| start >= end)	912✔
170	return true;	6✔
171
172	const auto lbound = arr.m_lbound;	906✔
173	const auto ubound = arr.m_ubound;	906✔
174
175	if (!c.can_match(value, lbound, ubound))	906✔
176	return true;	36✔
177
178	if (c.will_match(value, lbound, ubound)) {	870✔
179	return find_all_match(start, end, baseindex, state);	36✔
180	}	36✔
181
182	REALM_ASSERT_DEBUG(arr.m_width != 0);	834✔
183
184	const auto& compressor = arr.integer_compressor();	834✔
185	const auto v_width = arr.m_width;	834✔
186	const auto v_size = compressor.v_size();	834✔
187	const auto mask = compressor.v_mask();	834✔
188	uint64_t* data = (uint64_t*)arr.m_data;	834✔
189	size_t v_start = realm::not_found;	834✔
190
191	/************** Search the values **************/
192
193	int64_t modified_value = value;	834✔
194	if constexpr (std::is_same_v<Cond, Greater>) {	834✔
195	modified_value++; // We use GreaterEqual below, so this will effectively be Greater	690✔
196	}	690✔
197
198	if (v_size >= RANGE_LIMIT) {	834✔
199	if (v_width <= WIDTH_LIMIT) {	180✔
200	auto search_vector = populate(v_width, modified_value);	180✔
201	v_start = parallel_subword_find(find_all_fields<GreaterEqual>, data, 0, v_width, compressor.msb(),	180✔
202	search_vector, 0, v_size);	180✔
203	}	180✔
NEW 204	else {	×
NEW 205	BfIterator data_iterator{data, 0, v_width, v_width, 0};	×
NEW 206	v_start = lower_bound(v_size, modified_value, mask, data_iterator);	×
NEW 207	}	×
208	}	180✔
209	else {	654✔
210	BfIterator data_iterator{data, 0, v_width, v_width, 0};	654✔
211	size_t idx = 0;	654✔
212	while (idx < v_size) {	798!
213	if (sign_extend_field_by_mask(mask, *data_iterator) >= modified_value) {	798✔
214	break;	654✔
215	}	654✔
216	data_iterator.move(++idx);	144✔
217	}	144✔
218	v_start = idx;	654✔
219	}	654✔
220
221	if constexpr (realm::is_any_v<Cond, Equal, NotEqual>) {	834✔
222	// Check for equality.
223	if (v_start < v_size) {	60✔
224	BfIterator it{data, 0, v_width, v_width, v_start};	48✔
225	if (sign_extend_field_by_mask(mask, *it) > value) {	48✔
226	v_start = v_size; // Mark as not found	36✔
227	}	36✔
228	}	48✔
229	}	60✔
230
231	/*************** Some early outs ***************/
232
233	if (v_start == v_size) {	834✔
234	if constexpr (realm::is_any_v<Cond, Equal, Greater>) {	72✔
235	return true; // No Matches	36✔
236	}	36✔
237	if constexpr (realm::is_any_v<Cond, NotEqual, Less>) {	36✔
238	return find_all_match(start, end, baseindex, state); // All matches	36✔
239	}	36✔
240	}	36✔
241	else if (v_start == 0) {	762✔
242	if constexpr (std::is_same_v<Cond, Less>) {	654✔
243	// No index is less than 0
244	return true; // No Matches	12✔
245	}	12✔
246	if constexpr (std::is_same_v<Cond, Greater>) {	642✔
247	// All index is greater than or equal to 0
248	return find_all_match(start, end, baseindex, state);	642✔
249	}	642✔
250	}	327✔
251
252	/************* Search the indexes **************/
253
254	using U = typename IndexCond<Cond>::type;	54✔
255	const auto ndx_range = end - start;	471✔
256	const auto ndx_width = compressor.ndx_width();	471✔
257	const auto v_offset = v_size * v_width;	471✔
258	if (ndx_range >= RANGE_LIMIT) {	471✔
259	auto search_vector = populate(ndx_width, v_start);	108✔
260	while (start < end) {	8,970✔
261	start = parallel_subword_find(find_all_fields_unsigned<U>, data, v_offset, ndx_width,	8,886✔
262	compressor.ndx_msb(), search_vector, start, end);	8,886✔
263	if (start < end) {	8,886✔
264	if (!state->match(start + baseindex))	8,844✔
265	return false;	24✔
266	}	8,844✔
267	++start;	8,862✔
268	}	8,862✔
269	}	108✔
270	else {	363✔
271	U index_c;	363✔
272	BfIterator ndx_iterator{data, v_offset, ndx_width, ndx_width, start};	363✔
273	while (start < end) {	363✔
NEW 274	if (index_c(int64_t(*ndx_iterator), int64_t(v_start))) {	×
NEW 275	if (!state->match(start + baseindex))	×
NEW 276	return false;	×
NEW 277	}	×
NEW 278	ndx_iterator.move(++start);	×
NEW 279	}	×
280	}	363✔
281
282	return true;	447✔
283	}	471✔
284
285	} // namespace realm
286	#endif // FLEX_COMPRESSOR_HPP

realm / realm-core / jorgen.edelbo_389

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