jorgen.edelbo_333

Committed 01 Jul 2024 07:21AM UTC coverage: 90.865% (-0.08%) from 90.948%

Build # jorgen.edelbo_333

Build Type

Pull #7826

Evergreen

Committed by

jedelbo

Commit Message

Merge tag 'v14.10.2' into next-major

Pull Request Pull Request #7826: Merge Next major

Run Details

102912 of 181138 branches covered (56.81%)

3131 of 3738 new or added lines in 54 files covered. (83.76%)

80 existing lines in 14 files now uncovered.

217498 of 239364 relevant lines covered (90.86%)

6655796.15 hits per line

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

86.49

/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]);

    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::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
44	template <typename Cond>
45	static bool find_all(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
46
47	private:
48	static bool find_all_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state);
49
50	template <typename VectorCond>
51	static bool find_parallel(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
52
53	template <typename Cond>
54	static bool find_linear(const Array&, int64_t, size_t, size_t, size_t, QueryStateBase*);
55
56	template <typename Cond>
57	static bool run_parallel_scan(size_t, size_t);
58	};
59
60	inline int64_t PackedCompressor::get(const IntegerCompressor& c, size_t ndx)
61	{	64,545,219✔
62	BfIterator it{c.data(), 0, c.v_width(), c.v_width(), ndx};	64,545,219✔
63	return sign_extend_field_by_mask(c.v_mask(), *it);	64,545,219✔
64	}	64,545,219✔
65
66	inline std::vector<int64_t> PackedCompressor::get_all(const IntegerCompressor& c, size_t b, size_t e)
67	{	6✔
68	const auto range = (e - b);	6✔
69	const auto v_w = c.v_width();	6✔
70	const auto data = c.data();	6✔
71	const auto sign_mask = c.v_mask();	6✔
72	const auto starting_bit = b * v_w;	6✔
73	const auto total_bits = starting_bit + (v_w * range);	6✔
74	const auto mask = 0xFFFFFFFFFFFFFFFFULL >> (64 - v_w);	6✔
75	const auto bit_per_it = num_bits_for_width(v_w);	6✔
76	const auto values_per_word = num_fields_for_width(v_w);	6✔
77
78	std::vector<int64_t> res;	6✔
79	res.reserve(range);	6✔
80
81	UnalignedWordIter unaligned_data_iterator(data, starting_bit);	6✔
82	auto cnt_bits = starting_bit;	6✔
83	while (cnt_bits + bit_per_it < total_bits) {	96✔
84	auto word = unaligned_data_iterator.consume(bit_per_it);	90✔
85	for (int i = 0; i < values_per_word; ++i) {	180✔
86	res.push_back(sign_extend_field_by_mask(sign_mask, word & mask));	90✔
87	word >>= v_w;	90✔
88	}	90✔
89	cnt_bits += bit_per_it;	90✔
90	}	90✔
91	if (cnt_bits < total_bits) {	6✔
92	auto last_word = unaligned_data_iterator.consume(static_cast<unsigned>(total_bits - cnt_bits));	6✔
93	while (cnt_bits < total_bits) {	12✔
94	res.push_back(sign_extend_field_by_mask(sign_mask, last_word & mask));	6✔
95	cnt_bits += v_w;	6✔
96	last_word >>= v_w;	6✔
97	}	6✔
98	}	6✔
99	return res;	6✔
100	}	6✔
101
102	inline void PackedCompressor::get_chunk(const IntegerCompressor& c, size_t ndx, int64_t res[8])
NEW 103	{	×
NEW 104	auto sz = 8;	×
NEW 105	std::memset(res, 0, sizeof(int64_t) * sz);	×
NEW 106	auto supposed_end = ndx + sz;	×
NEW 107	size_t i = ndx;	×
NEW 108	size_t index = 0;	×
109	// this can be done better, in one go, retrieve both!!!
NEW 110	for (; i < supposed_end; ++i) {	×
NEW 111	res[index++] = get(c, i);	×
NEW 112	}	×
NEW 113	for (; index < 8; ++index) {	×
NEW 114	res[index++] = get(c, i++);	×
NEW 115	}	×
NEW 116	}	×
117
118
119	template <typename Cond>
120	inline bool PackedCompressor::find_all(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
121	QueryStateBase* state)
122	{	4,960,098✔
123	REALM_ASSERT_DEBUG(start <= arr.m_size && (end <= arr.m_size \|\| end == size_t(-1)) && start <= end);	4,960,098!
124	Cond c;	4,960,098✔
125
126	if (end == npos)	4,960,098✔
NEW 127	end = arr.m_size;	×
128
129	if (!(arr.m_size > start && start < end))	5,462,169✔
130	return true;	1,326✔
131
132	const auto lbound = arr.m_lbound;	4,958,772✔
133	const auto ubound = arr.m_ubound;	4,958,772✔
134
135	if (!c.can_match(value, lbound, ubound))	4,958,772✔
136	return true;	1,945,581✔
137
138	if (c.will_match(value, lbound, ubound)) {	3,013,191✔
139	return find_all_match(start, end, baseindex, state);	23,256✔
140	}	23,256✔
141
142	REALM_ASSERT_DEBUG(arr.m_width != 0);	2,989,935✔
143
144	if (!run_parallel_scan<Cond>(arr.m_width, end - start))	2,989,935✔
145	return find_linear<Cond>(arr, value, start, end, baseindex, state);	22,908✔
146
147	return find_parallel<Cond>(arr, value, start, end, baseindex, state);	2,967,027✔
148	}	2,989,935✔
149
150	template <typename VectorCond>
151	inline bool PackedCompressor::find_parallel(const Array& arr, int64_t value, size_t start, size_t end,
152	size_t baseindex, QueryStateBase* state)
153	{	3,561,708✔
154	//
155	// Main idea around find parallel (applicable to flex arrays too).
156	// Try to find the starting point where the condition can be met, comparing as many values as a single 64bit can
157	// contain in parallel. Once we have found the starting point, keep matching values as much as we can between
158	// start and end.
159	//
160	// EG: let's store 6, it gets stored in 4 bits (0110). 6 is 4 bits because 110 (6) + sign bit 0.
161	// 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
162	// apply a mask and a shift bits every time, then compare the extracted values.
163	// This is not the cheapest thing to do. Instead we can compare all values contained within 64 bits in one go, and
164	// see if there is a match with what we are looking for. Reducing the number of comparison by ~logk(N) where K is
165	// the width of each single value within a 64 bit word and N is the total number of values stored in the array.
166
167	const auto data = (const uint64_t*)arr.m_data;	3,561,708✔
168	const auto width = arr.m_width;	3,561,708✔
169	const auto MSBs = arr.integer_compressor().msb();	3,561,708✔
170	const auto search_vector = populate(arr.m_width, value);	3,561,708✔
171	while (start < end) {	14,284,323✔
172	start = parallel_subword_find(find_all_fields<VectorCond>, data, 0, width, MSBs, search_vector, start, end);	10,744,557✔
173	if (start < end && !state->match(start + baseindex))	10,744,557✔
174	return false;	21,942✔
175	++start;	10,722,615✔
176	}	10,722,615✔
177	return true;	3,539,766✔
178	}	3,561,708✔
179
180	template <typename Cond>
181	inline bool PackedCompressor::find_linear(const Array& arr, int64_t value, size_t start, size_t end, size_t baseindex,
182	QueryStateBase* state)
183	{	22,908✔
184	auto compare = [](int64_t a, int64_t b) {	6,085,890✔
185	if constexpr (std::is_same_v<Cond, Equal>)	3,077,466✔
186	return a == b;	162✔
187	if constexpr (std::is_same_v<Cond, NotEqual>)	3,077,385✔
188	return a != b;	6,073,857✔
189	if constexpr (std::is_same_v<Cond, Greater>)	2,147,483,647✔
190	return a > b;	11,946✔
191	if constexpr (std::is_same_v<Cond, Less>)	2,147,483,647✔
NEW 192	return a < b;	×
193	};	3,008,424✔
194	const auto& c = arr.integer_compressor();	22,908✔
195	BfIterator it{c.data(), 0, c.v_width(), c.v_width(), start};	22,908✔
196	for (; start < end; ++start) {	6,094,431✔
197	it.move(start);	6,085,833✔
198	const auto sv = sign_extend_field_by_mask(c.v_mask(), *it);	6,085,833✔
199	if (compare(sv, value) && !state->match(start + baseindex))	6,085,833!
200	return false;	14,310✔
201	}	6,085,833✔
202	return true;	8,598✔
203	}	22,908✔
204
205	template <typename Cond>
206	inline bool PackedCompressor::run_parallel_scan(size_t width, size_t range)
207	{	3,763,008✔
208	if constexpr (std::is_same_v<Cond, NotEqual>) {	3,763,008✔
209	// we seem to be particularly slow doing parallel scan in packed for NotEqual.
210	// we are much better with a linear scan. TODO: investigate this.
211	return false;	11,676✔
212	}	11,676✔
213	if constexpr (std::is_same_v<Cond, Equal>) {	3,729,819✔
214	return width < 32 && range >= 20;	3,814,086✔
215	}	3,707,517✔
216	// > and < need a different heuristic
217	return width <= 20 && range >= 20;	1,830,435!
218	}	3,763,008✔
219
220	} // namespace realm
221
222	#endif // PACKED_COMPRESSOR_HPP

realm / realm-core / jorgen.edelbo_333

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