jorgen.edelbo_390

Committed 12 Aug 2024 12:13PM UTC coverage: 91.108% (+0.02%) from 91.085%

Build # jorgen.edelbo_390

Build Type

Pull #7979

Evergreen

Committed by

jedelbo

Commit Message

Create test file in file-format 24

Pull Request Pull Request #7979: Create test file in file-format 24

Run Details

102766 of 181590 branches covered (56.59%)

19 of 19 new or added lines in 1 file covered. (100.0%)

1020 existing lines in 55 files now uncovered.

217365 of 238579 relevant lines covered (91.11%)

5621116.99 hits per line

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

97.41

/src/realm/array_direct.hpp

/*************************************************************************
 *
 * Copyright 2016 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 REALM_ARRAY_DIRECT_HPP
#define REALM_ARRAY_DIRECT_HPP

#include <realm/utilities.hpp>
#include <realm/alloc.hpp>

// clang-format off
/* wid == 16/32 likely when accessing offsets in B tree */
#define REALM_TEMPEX(fun, wid, arg) \
    if (wid == 16) {fun<16> arg;} \
    else if (wid == 32) {fun<32> arg;} \
    else if (wid == 0) {fun<0> arg;} \
    else if (wid == 1) {fun<1> arg;} \
    else if (wid == 2) {fun<2> arg;} \
    else if (wid == 4) {fun<4> arg;} \
    else if (wid == 8) {fun<8> arg;} \
    else if (wid == 64) {fun<64> arg;} \
    else {REALM_ASSERT_DEBUG(false); fun<0> arg;}

#define REALM_TEMPEX2(fun, targ, wid, arg) \
    if (wid == 16) {fun<targ, 16> arg;} \
    else if (wid == 32) {fun<targ, 32> arg;} \
    else if (wid == 0) {fun<targ, 0> arg;} \
    else if (wid == 1) {fun<targ, 1> arg;} \
    else if (wid == 2) {fun<targ, 2> arg;} \
    else if (wid == 4) {fun<targ, 4> arg;} \
    else if (wid == 8) {fun<targ, 8> arg;} \
    else if (wid == 64) {fun<targ, 64> arg;} \
    else {REALM_ASSERT_DEBUG(false); fun<targ, 0> arg;}

#define REALM_TEMPEX3(fun, targ1, wid, targ3, arg) \
    if (wid == 16) {fun<targ1, 16, targ3> arg;} \
    else if (wid == 32) {fun<targ1, 32, targ3> arg;} \
    else if (wid == 0) {fun<targ1, 0, targ3> arg;} \
    else if (wid == 1) {fun<targ1, 1, targ3> arg;} \
    else if (wid == 2) {fun<targ1, 2, targ3> arg;} \
    else if (wid == 4) {fun<targ1, 4, targ3> arg;} \
    else if (wid == 8) {fun<targ1, 8, targ3> arg;} \
    else if (wid == 64) {fun<targ1, 64, targ3> arg;} \
    else {REALM_ASSERT_DEBUG(false); fun<targ1, 0, targ3> arg;}

#define REALM_TEMPEX4(fun, targ1, targ3, targ4, wid, arg) \
    if (wid == 16) {fun<targ1, targ3, targ4, 16> arg;} \
    else if (wid == 32) {fun<targ1, targ3, targ4, 32> arg;} \
    else if (wid == 0) {fun<targ1, targ3, targ4, 0> arg;} \
    else if (wid == 1) {fun<targ1, targ3, targ4, 1> arg;} \
    else if (wid == 2) {fun<targ1, targ3, targ4, 2> arg;} \
    else if (wid == 4) {fun<targ1, targ3, targ4, 4> arg;} \
    else if (wid == 8) {fun<targ1, targ3, targ4, 8> arg;} \
    else if (wid == 64) {fun<targ1, targ3, targ4, 64> arg;} \
    else {REALM_ASSERT_DEBUG(false); fun<targ1, targ3, targ4, 0> arg;}
// clang-format on

namespace realm {

/// Takes a 64-bit value and returns the minimum number of bits needed
/// to fit the value. For alignment this is rounded up to nearest
/// log2. Posssible results {0, 1, 2, 4, 8, 16, 32, 64}
size_t bit_width(int64_t value);

// Direct access methods

template <size_t width>
void set_direct(char* data, size_t ndx, int_fast64_t value) noexcept
{
    if (width == 0) {
        REALM_ASSERT_DEBUG(value == 0);
        return;
    }
    else if (width == 1) {
        REALM_ASSERT_DEBUG(0 <= value && value <= 0x01);
        size_t byte_ndx = ndx / 8;
        size_t bit_ndx = ndx % 8;
        typedef unsigned char uchar;
        uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;
        *p = uchar((*p & ~(0x01 << bit_ndx)) | (int(value) & 0x01) << bit_ndx);
    }
    else if (width == 2) {
        REALM_ASSERT_DEBUG(0 <= value && value <= 0x03);
        size_t byte_ndx = ndx / 4;
        size_t bit_ndx = ndx % 4 * 2;
        typedef unsigned char uchar;
        uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;
        *p = uchar((*p & ~(0x03 << bit_ndx)) | (int(value) & 0x03) << bit_ndx);
    }
    else if (width == 4) {
        REALM_ASSERT_DEBUG(0 <= value && value <= 0x0F);
        size_t byte_ndx = ndx / 2;
        size_t bit_ndx = ndx % 2 * 4;
        typedef unsigned char uchar;
        uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;
        *p = uchar((*p & ~(0x0F << bit_ndx)) | (int(value) & 0x0F) << bit_ndx);
    }
    else if (width == 8) {
        REALM_ASSERT_DEBUG(std::numeric_limits<int8_t>::min() <= value &&
                           value <= std::numeric_limits<int8_t>::max());
        *(reinterpret_cast<int8_t*>(data) + ndx) = int8_t(value);
    }
    else if (width == 16) {
        REALM_ASSERT_DEBUG(std::numeric_limits<int16_t>::min() <= value &&
                           value <= std::numeric_limits<int16_t>::max());
        *(reinterpret_cast<int16_t*>(data) + ndx) = int16_t(value);
    }
    else if (width == 32) {
        REALM_ASSERT_DEBUG(std::numeric_limits<int32_t>::min() <= value &&
                           value <= std::numeric_limits<int32_t>::max());
        *(reinterpret_cast<int32_t*>(data) + ndx) = int32_t(value);
    }
    else if (width == 64) {
        REALM_ASSERT_DEBUG(std::numeric_limits<int64_t>::min() <= value &&
                           value <= std::numeric_limits<int64_t>::max());
        *(reinterpret_cast<int64_t*>(data) + ndx) = int64_t(value);
    }
    else {
        REALM_ASSERT_DEBUG(false);
    }
}

inline void set_direct(char* data, size_t width, size_t ndx, int_fast64_t value) noexcept
{
    REALM_TEMPEX(set_direct, width, (data, ndx, value));
}

template <size_t width>
void fill_direct(char* data, size_t begin, size_t end, int_fast64_t value) noexcept
{
    for (size_t i = begin; i != end; ++i)
        set_direct<width>(data, i, value);
}

template <int w>
int64_t get_direct(const char* data, size_t ndx) noexcept
{
    if (w == 0) {
        return 0;
    }
    if (w == 1) {
        size_t offset = ndx >> 3;
        return (data[offset] >> (ndx & 7)) & 0x01;
    }
    if (w == 2) {
        size_t offset = ndx >> 2;
        return (data[offset] >> ((ndx & 3) << 1)) & 0x03;
    }
    if (w == 4) {
        size_t offset = ndx >> 1;
        return (data[offset] >> ((ndx & 1) << 2)) & 0x0F;
    }
    if (w == 8) {
        return *reinterpret_cast<const signed char*>(data + ndx);
    }
    if (w == 16) {
        size_t offset = ndx * 2;
        return *reinterpret_cast<const int16_t*>(data + offset);
    }
    if (w == 32) {
        size_t offset = ndx * 4;
        return *reinterpret_cast<const int32_t*>(data + offset);
    }
    if (w == 64) {
        size_t offset = ndx * 8;
        return *reinterpret_cast<const int64_t*>(data + offset);
    }
    REALM_ASSERT_DEBUG(false);
    return int64_t(-1);
}

inline int64_t get_direct(const char* data, size_t width, size_t ndx) noexcept
{
    REALM_TEMPEX(return get_direct, width, (data, ndx));
}


template <int width>
inline std::pair<int64_t, int64_t> get_two(const char* data, size_t ndx) noexcept
{
    return std::make_pair(to_size_t(get_direct<width>(data, ndx + 0)), to_size_t(get_direct<width>(data, ndx + 1)));
}

inline std::pair<int64_t, int64_t> get_two(const char* data, size_t width, size_t ndx) noexcept
{
    REALM_TEMPEX(return get_two, width, (data, ndx));
}


// Lower/upper bound in sorted sequence
// ------------------------------------
//
//   3 3 3 4 4 4 5 6 7 9 9 9
//   ^     ^     ^     ^     ^
//   |     |     |     |     |
//   |     |     |     |      -- Lower and upper bound of 15
//   |     |     |     |
//   |     |     |      -- Lower and upper bound of 8
//   |     |     |
//   |     |      -- Upper bound of 4
//   |     |
//   |      -- Lower bound of 4
//   |
//    -- Lower and upper bound of 1
//
// These functions are semantically identical to std::lower_bound() and
// std::upper_bound().
//
// We currently use binary search. See for example
// http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary.
template <int width>
inline size_t lower_bound(const char* data, size_t size, int64_t value) noexcept
{
    // The binary search used here is carefully optimized. Key trick is to use a single
    // loop controlling variable (size) instead of high/low pair, and to keep updates
    // to size done inside the loop independent of comparisons. Further key to speed
    // is to avoid branching inside the loop, using conditional moves instead. This
    // provides robust performance for random searches, though predictable searches
    // might be slightly faster if we used branches instead. The loop unrolling yields
    // a final 5-20% speedup depending on circumstances.

    size_t low = 0;

    while (size >= 8) {
        // The following code (at X, Y and Z) is 3 times manually unrolled instances of (A) below.
        // These code blocks must be kept in sync. Meassurements indicate 3 times unrolling to give
        // the best performance. See (A) for comments on the loop body.
        // (X)
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        int64_t v = get_direct<width>(data, probe);
        size = half;
        low = (v < value) ? other_low : low;

        // (Y)
        half = size / 2;
        other_half = size - half;
        probe = low + half;
        other_low = low + other_half;
        v = get_direct<width>(data, probe);
        size = half;
        low = (v < value) ? other_low : low;

        // (Z)
        half = size / 2;
        other_half = size - half;
        probe = low + half;
        other_low = low + other_half;
        v = get_direct<width>(data, probe);
        size = half;
        low = (v < value) ? other_low : low;
    }
    while (size > 0) {
        // (A)
        // To understand the idea in this code, please note that
        // for performance, computation of size for the next iteration
        // MUST be INDEPENDENT of the conditional. This allows the
        // processor to unroll the loop as fast as possible, and it
        // minimizes the length of dependence chains leading up to branches.
        // Making the unfolding of the loop independent of the data being
        // searched, also minimizes the delays incurred by branch
        // mispredictions, because they can be determined earlier
        // and the speculation corrected earlier.

        // Counterintuitive:
        // To make size independent of data, we cannot always split the
        // range at the theoretical optimal point. When we determine that
        // the key is larger than the probe at some index K, and prepare
        // to search the upper part of the range, you would normally start
        // the search at the next index, K+1, to get the shortest range.
        // We can only do this when splitting a range with odd number of entries.
        // If there is an even number of entries we search from K instead of K+1.
        // This potentially leads to redundant comparisons, but in practice we
        // gain more performance by making the changes to size predictable.

        // if size is even, half and other_half are the same.
        // if size is odd, half is one less than other_half.
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        int64_t v = get_direct<width>(data, probe);
        size = half;
        // for max performance, the line below should compile into a conditional
        // move instruction. Not all compilers do this. To maximize chance
        // of succes, no computation should be done in the branches of the
        // conditional.
        low = (v < value) ? other_low : low;
    };

    return low;
}

// See lower_bound()
template <int width>
inline size_t upper_bound(const char* data, size_t size, int64_t value) noexcept
{
    size_t low = 0;
    while (size >= 8) {
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        int64_t v = get_direct<width>(data, probe);
        size = half;
        low = (value >= v) ? other_low : low;

        half = size / 2;
        other_half = size - half;
        probe = low + half;
        other_low = low + other_half;
        v = get_direct<width>(data, probe);
        size = half;
        low = (value >= v) ? other_low : low;

        half = size / 2;
        other_half = size - half;
        probe = low + half;
        other_low = low + other_half;
        v = get_direct<width>(data, probe);
        size = half;
        low = (value >= v) ? other_low : low;
    }

    while (size > 0) {
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        int64_t v = get_direct<width>(data, probe);
        size = half;
        low = (value >= v) ? other_low : low;
    };

    return low;
}
} // namespace realm

#endif /* ARRAY_TPL_HPP_ */

1	/*************************************************************************
2	*
3	* Copyright 2016 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 REALM_ARRAY_DIRECT_HPP
20	#define REALM_ARRAY_DIRECT_HPP
21
22	#include <realm/utilities.hpp>
23	#include <realm/alloc.hpp>
24
25	// clang-format off
26	/* wid == 16/32 likely when accessing offsets in B tree */
27	#define REALM_TEMPEX(fun, wid, arg) \
28	if (wid == 16) {fun<16> arg;} \	2,089,938,813✔
29	else if (wid == 32) {fun<32> arg;} \	2,089,938,813✔
30	else if (wid == 0) {fun<0> arg;} \	1,733,758,086✔
31	else if (wid == 1) {fun<1> arg;} \	727,987,014✔
32	else if (wid == 2) {fun<2> arg;} \	660,045,165✔
33	else if (wid == 4) {fun<4> arg;} \	475,113,306✔
34	else if (wid == 8) {fun<8> arg;} \	314,164,260✔
35	else if (wid == 64) {fun<64> arg;} \	293,725,986✔
36	else {REALM_ASSERT_DEBUG(false); fun<0> arg;}	4,294,967,294✔
37
38	#define REALM_TEMPEX2(fun, targ, wid, arg) \
39	if (wid == 16) {fun<targ, 16> arg;} \	6,768,873✔
40	else if (wid == 32) {fun<targ, 32> arg;} \	2,151,402,988✔
41	else if (wid == 0) {fun<targ, 0> arg;} \	2,148,382,813✔
42	else if (wid == 1) {fun<targ, 1> arg;} \	2,148,364,714✔
43	else if (wid == 2) {fun<targ, 2> arg;} \	2,148,352,780✔
44	else if (wid == 4) {fun<targ, 4> arg;} \	2,148,298,384✔
45	else if (wid == 8) {fun<targ, 8> arg;} \	2,147,937,718✔
46	else if (wid == 64) {fun<targ, 64> arg;} \	4,294,967,294✔
47	else {REALM_ASSERT_DEBUG(false); fun<targ, 0> arg;}	4,294,967,294✔
48
49	#define REALM_TEMPEX3(fun, targ1, wid, targ3, arg) \
50	if (wid == 16) {fun<targ1, 16, targ3> arg;} \
51	else if (wid == 32) {fun<targ1, 32, targ3> arg;} \
52	else if (wid == 0) {fun<targ1, 0, targ3> arg;} \
53	else if (wid == 1) {fun<targ1, 1, targ3> arg;} \
54	else if (wid == 2) {fun<targ1, 2, targ3> arg;} \
55	else if (wid == 4) {fun<targ1, 4, targ3> arg;} \
56	else if (wid == 8) {fun<targ1, 8, targ3> arg;} \
57	else if (wid == 64) {fun<targ1, 64, targ3> arg;} \
58	else {REALM_ASSERT_DEBUG(false); fun<targ1, 0, targ3> arg;}
59
60	#define REALM_TEMPEX4(fun, targ1, targ3, targ4, wid, arg) \
61	if (wid == 16) {fun<targ1, targ3, targ4, 16> arg;} \
62	else if (wid == 32) {fun<targ1, targ3, targ4, 32> arg;} \
63	else if (wid == 0) {fun<targ1, targ3, targ4, 0> arg;} \
64	else if (wid == 1) {fun<targ1, targ3, targ4, 1> arg;} \
65	else if (wid == 2) {fun<targ1, targ3, targ4, 2> arg;} \
66	else if (wid == 4) {fun<targ1, targ3, targ4, 4> arg;} \
67	else if (wid == 8) {fun<targ1, targ3, targ4, 8> arg;} \
68	else if (wid == 64) {fun<targ1, targ3, targ4, 64> arg;} \
69	else {REALM_ASSERT_DEBUG(false); fun<targ1, targ3, targ4, 0> arg;}
70	// clang-format on
71
72	namespace realm {
73
74	/// Takes a 64-bit value and returns the minimum number of bits needed
75	/// to fit the value. For alignment this is rounded up to nearest
76	/// log2. Posssible results {0, 1, 2, 4, 8, 16, 32, 64}
77	size_t bit_width(int64_t value);
78
79	// Direct access methods
80
81	template <size_t width>
82	void set_direct(char* data, size_t ndx, int_fast64_t value) noexcept
83	{	1,197,603,276✔
84	if (width == 0) {	1,197,603,276✔
85	REALM_ASSERT_DEBUG(value == 0);	31,748,184!
86	return;	31,748,184✔
87	}	31,748,184✔
88	else if (width == 1) {	1,165,855,092✔
89	REALM_ASSERT_DEBUG(0 <= value && value <= 0x01);	164,269,986!
90	size_t byte_ndx = ndx / 8;	164,269,986✔
91	size_t bit_ndx = ndx % 8;	164,269,986✔
92	typedef unsigned char uchar;	164,269,986✔
93	uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;	164,269,986✔
94	p = uchar((p & ~(0x01 << bit_ndx)) \| (int(value) & 0x01) << bit_ndx);	164,269,986✔
95	}	164,269,986✔
96	else if (width == 2) {	1,001,585,106✔
97	REALM_ASSERT_DEBUG(0 <= value && value <= 0x03);	142,873,209!
98	size_t byte_ndx = ndx / 4;	142,873,209✔
99	size_t bit_ndx = ndx % 4 * 2;	142,873,209✔
100	typedef unsigned char uchar;	142,873,209✔
101	uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;	142,873,209✔
102	p = uchar((p & ~(0x03 << bit_ndx)) \| (int(value) & 0x03) << bit_ndx);	142,873,209✔
103	}	142,873,209✔
104	else if (width == 4) {	858,711,897✔
105	REALM_ASSERT_DEBUG(0 <= value && value <= 0x0F);	9,842,175!
106	size_t byte_ndx = ndx / 2;	9,842,175✔
107	size_t bit_ndx = ndx % 2 * 4;	9,842,175✔
108	typedef unsigned char uchar;	9,842,175✔
109	uchar* p = reinterpret_cast<uchar*>(data) + byte_ndx;	9,842,175✔
110	p = uchar((p & ~(0x0F << bit_ndx)) \| (int(value) & 0x0F) << bit_ndx);	9,842,175✔
111	}	9,842,175✔
112	else if (width == 8) {	848,869,722✔
113	REALM_ASSERT_DEBUG(std::numeric_limits<int8_t>::min() <= value &&	144,169,626!
114	value <= std::numeric_limits<int8_t>::max());	144,169,626✔
115	(reinterpret_cast<int8_t>(data) + ndx) = int8_t(value);	144,169,626✔
116	}	144,169,626✔
117	else if (width == 16) {	704,700,096✔
118	REALM_ASSERT_DEBUG(std::numeric_limits<int16_t>::min() <= value &&	230,239,065!
119	value <= std::numeric_limits<int16_t>::max());	230,239,065✔
120	(reinterpret_cast<int16_t>(data) + ndx) = int16_t(value);	230,239,065✔
121	}	230,239,065✔
122	else if (width == 32) {	474,461,031✔
123	REALM_ASSERT_DEBUG(std::numeric_limits<int32_t>::min() <= value &&	374,115,711!
124	value <= std::numeric_limits<int32_t>::max());	374,115,711✔
125	(reinterpret_cast<int32_t>(data) + ndx) = int32_t(value);	374,115,711✔
126	}	374,115,711✔
127	else if (width == 64) {	100,345,320✔
128	REALM_ASSERT_DEBUG(std::numeric_limits<int64_t>::min() <= value &&	100,295,124!
129	value <= std::numeric_limits<int64_t>::max());	100,295,124✔
130	(reinterpret_cast<int64_t>(data) + ndx) = int64_t(value);	100,295,124✔
131	}	100,295,124✔
132	else {	50,196✔
133	REALM_ASSERT_DEBUG(false);	50,196✔
134	}	50,196✔
135	}	1,197,603,276✔
136
137	inline void set_direct(char* data, size_t width, size_t ndx, int_fast64_t value) noexcept
UNCOV 138	{	×
UNCOV 139	REALM_TEMPEX(set_direct, width, (data, ndx, value));	×
UNCOV 140	}	×
141
142	template <size_t width>
143	void fill_direct(char* data, size_t begin, size_t end, int_fast64_t value) noexcept
144	{	178,632✔
145	for (size_t i = begin; i != end; ++i)	192,024!
146	set_direct<width>(data, i, value);	13,392✔
147	}	178,632✔
148
149	template <int w>
150	int64_t get_direct(const char* data, size_t ndx) noexcept
151	{	601,773,645✔
152	if (w == 0) {	601,773,645✔
153	return 0;	2,610,126✔
154	}	2,610,126✔
155	if (w == 1) {	599,163,519✔
156	size_t offset = ndx >> 3;	1,650,201✔
157	return (data[offset] >> (ndx & 7)) & 0x01;	1,650,201✔
158	}	1,650,201✔
159	if (w == 2) {	597,513,318✔
160	size_t offset = ndx >> 2;	7,196,784✔
161	return (data[offset] >> ((ndx & 3) << 1)) & 0x03;	7,196,784✔
162	}	7,196,784✔
163	if (w == 4) {	590,316,534✔
164	size_t offset = ndx >> 1;	1,119,867✔
165	return (data[offset] >> ((ndx & 1) << 2)) & 0x0F;	1,119,867✔
166	}	1,119,867✔
167	if (w == 8) {	589,196,667✔
168	return reinterpret_cast<const signed char>(data + ndx);	35,819,043✔
169	}	35,819,043✔
170	if (w == 16) {	553,377,624✔
171	size_t offset = ndx * 2;	57,789,648✔
172	return reinterpret_cast<const int16_t>(data + offset);	57,789,648✔
173	}	57,789,648✔
174	if (w == 32) {	495,587,976✔
175	size_t offset = ndx * 4;	417,458,907✔
176	return reinterpret_cast<const int32_t>(data + offset);	417,458,907✔
177	}	417,458,907✔
178	if (w == 64) {	78,368,676✔
179	size_t offset = ndx * 8;	78,298,779✔
180	return reinterpret_cast<const int64_t>(data + offset);	78,298,779✔
181	}	78,298,779✔
182	REALM_ASSERT_DEBUG(false);	2,147,553,544✔
183	return int64_t(-1);	2,147,553,544✔
184	}	78,129,069✔
185
186	inline int64_t get_direct(const char* data, size_t width, size_t ndx) noexcept
187	{	350,606,166✔
188	REALM_TEMPEX(return get_direct, width, (data, ndx));	350,606,166✔
UNCOV 189	}	×
190
191
192	template <int width>
193	inline std::pair<int64_t, int64_t> get_two(const char* data, size_t ndx) noexcept
194	{	863,433✔
195	return std::make_pair(to_size_t(get_direct<width>(data, ndx + 0)), to_size_t(get_direct<width>(data, ndx + 1)));	863,433✔
196	}	863,433✔
197
198	inline std::pair<int64_t, int64_t> get_two(const char* data, size_t width, size_t ndx) noexcept
199	{	863,433✔
200	REALM_TEMPEX(return get_two, width, (data, ndx));	863,433✔
UNCOV 201	}	×
202
203
204	// Lower/upper bound in sorted sequence
205	// ------------------------------------
206	//
207	// 3 3 3 4 4 4 5 6 7 9 9 9
208	// ^ ^ ^ ^ ^
209	// \| \| \| \| \|
210	// \| \| \| \| -- Lower and upper bound of 15
211	// \| \| \| \|
212	// \| \| \| -- Lower and upper bound of 8
213	// \| \| \|
214	// \| \| -- Upper bound of 4
215	// \| \|
216	// \| -- Lower bound of 4
217	// \|
218	// -- Lower and upper bound of 1
219	//
220	// These functions are semantically identical to std::lower_bound() and
221	// std::upper_bound().
222	//
223	// We currently use binary search. See for example
224	// http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary.
225	template <int width>
226	inline size_t lower_bound(const char* data, size_t size, int64_t value) noexcept
227	{	20,782,881✔
228	// The binary search used here is carefully optimized. Key trick is to use a single
229	// loop controlling variable (size) instead of high/low pair, and to keep updates
230	// to size done inside the loop independent of comparisons. Further key to speed
231	// is to avoid branching inside the loop, using conditional moves instead. This
232	// provides robust performance for random searches, though predictable searches
233	// might be slightly faster if we used branches instead. The loop unrolling yields
234	// a final 5-20% speedup depending on circumstances.
235
236	size_t low = 0;	20,782,881✔
237
238	while (size >= 8) {	30,222,837✔
239	// The following code (at X, Y and Z) is 3 times manually unrolled instances of (A) below.
240	// These code blocks must be kept in sync. Meassurements indicate 3 times unrolling to give
241	// the best performance. See (A) for comments on the loop body.
242	// (X)
243	size_t half = size / 2;	9,439,956✔
244	size_t other_half = size - half;	9,439,956✔
245	size_t probe = low + half;	9,439,956✔
246	size_t other_low = low + other_half;	9,439,956✔
247	int64_t v = get_direct<width>(data, probe);	9,439,956✔
248	size = half;	9,439,956✔
249	low = (v < value) ? other_low : low;	9,439,956!
250
251	// (Y)
252	half = size / 2;	9,439,956✔
253	other_half = size - half;	9,439,956✔
254	probe = low + half;	9,439,956✔
255	other_low = low + other_half;	9,439,956✔
256	v = get_direct<width>(data, probe);	9,439,956✔
257	size = half;	9,439,956✔
258	low = (v < value) ? other_low : low;	9,439,956!
259
260	// (Z)
261	half = size / 2;	9,439,956✔
262	other_half = size - half;	9,439,956✔
263	probe = low + half;	9,439,956✔
264	other_low = low + other_half;	9,439,956✔
265	v = get_direct<width>(data, probe);	9,439,956✔
266	size = half;	9,439,956✔
267	low = (v < value) ? other_low : low;	9,439,956!
268	}	9,439,956✔
269	while (size > 0) {	54,105,771✔
270	// (A)
271	// To understand the idea in this code, please note that
272	// for performance, computation of size for the next iteration
273	// MUST be INDEPENDENT of the conditional. This allows the
274	// processor to unroll the loop as fast as possible, and it
275	// minimizes the length of dependence chains leading up to branches.
276	// Making the unfolding of the loop independent of the data being
277	// searched, also minimizes the delays incurred by branch
278	// mispredictions, because they can be determined earlier
279	// and the speculation corrected earlier.
280
281	// Counterintuitive:
282	// To make size independent of data, we cannot always split the
283	// range at the theoretical optimal point. When we determine that
284	// the key is larger than the probe at some index K, and prepare
285	// to search the upper part of the range, you would normally start
286	// the search at the next index, K+1, to get the shortest range.
287	// We can only do this when splitting a range with odd number of entries.
288	// If there is an even number of entries we search from K instead of K+1.
289	// This potentially leads to redundant comparisons, but in practice we
290	// gain more performance by making the changes to size predictable.
291
292	// if size is even, half and other_half are the same.
293	// if size is odd, half is one less than other_half.
294	size_t half = size / 2;	33,322,890✔
295	size_t other_half = size - half;	33,322,890✔
296	size_t probe = low + half;	33,322,890✔
297	size_t other_low = low + other_half;	33,322,890✔
298	int64_t v = get_direct<width>(data, probe);	33,322,890✔
299	size = half;	33,322,890✔
300	// for max performance, the line below should compile into a conditional
301	// move instruction. Not all compilers do this. To maximize chance
302	// of succes, no computation should be done in the branches of the
303	// conditional.
304	low = (v < value) ? other_low : low;	33,322,890✔
305	};	33,322,890✔
306
307	return low;	20,782,881✔
308	}	20,782,881✔
309
310	// See lower_bound()
311	template <int width>
312	inline size_t upper_bound(const char* data, size_t size, int64_t value) noexcept
313	{	5,424,372✔
314	size_t low = 0;	5,424,372✔
315	while (size >= 8) {	16,923,042✔
316	size_t half = size / 2;	11,498,670✔
317	size_t other_half = size - half;	11,498,670✔
318	size_t probe = low + half;	11,498,670✔
319	size_t other_low = low + other_half;	11,498,670✔
320	int64_t v = get_direct<width>(data, probe);	11,498,670✔
321	size = half;	11,498,670✔
322	low = (value >= v) ? other_low : low;	11,498,670!
323
324	half = size / 2;	11,498,670✔
325	other_half = size - half;	11,498,670✔
326	probe = low + half;	11,498,670✔
327	other_low = low + other_half;	11,498,670✔
328	v = get_direct<width>(data, probe);	11,498,670✔
329	size = half;	11,498,670✔
330	low = (value >= v) ? other_low : low;	11,498,670!
331
332	half = size / 2;	11,498,670✔
333	other_half = size - half;	11,498,670✔
334	probe = low + half;	11,498,670✔
335	other_low = low + other_half;	11,498,670✔
336	v = get_direct<width>(data, probe);	11,498,670✔
337	size = half;	11,498,670✔
338	low = (value >= v) ? other_low : low;	11,498,670!
339	}	11,498,670✔
340
341	while (size > 0) {	15,354,921✔
342	size_t half = size / 2;	9,930,549✔
343	size_t other_half = size - half;	9,930,549✔
344	size_t probe = low + half;	9,930,549✔
345	size_t other_low = low + other_half;	9,930,549✔
346	int64_t v = get_direct<width>(data, probe);	9,930,549✔
347	size = half;	9,930,549✔
348	low = (value >= v) ? other_low : low;	9,930,549✔
349	};	9,930,549✔
350
351	return low;	5,424,372✔
352	}	5,424,372✔
353	} // namespace realm
354
355	#endif /* ARRAY_TPL_HPP_ */

realm / realm-core / jorgen.edelbo_390

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