Skip to content

Commit d7c8339

Browse files
jkeiserjkeiser
committed
lookup+cont-check algorithm
1 parent 1d621bb commit d7c8339

11 files changed

Lines changed: 553 additions & 21 deletions

File tree

‎.gitignore‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,8 +55,11 @@ objs
5555
/basictests
5656
/benchfeatures
5757
/benchmark/parse
58+
/benchmark/parse_stream
5859
/benchmark/perfdiff
5960
/benchmark/statisticalmodel
61+
/fuzz/fuzz_dump
62+
/fuzz/fuzz_parser
6063
/json2json
6164
/jsoncheck
6265
/jsoncheck_noavx
@@ -85,6 +88,7 @@ objs
8588
/tests/integer_tests
8689
/tools/json2json
8790
/tools/jsonstats
91+
/tests/jsonstream_test
8892
/tools/minify
8993

9094
# Don't check in generated examples

‎Makefile‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,12 @@ COMPARISONEXECUTABLES=minifiercompetition parsingcompetition parseandstatcompeti
6464
SUPPLEMENTARYEXECUTABLES=parse_noutf8validation parse_nonumberparsing parse_nostringparsing
6565

6666
# Load headers and sources
67-
LIBHEADERS=src/simdprune_tables.h src/arm64/bitmanipulation.h src/haswell/bitmanipulation.h src/westmere/bitmanipulation.h src/simdprune_tables.h src/arm64/numberparsing.h src/generic/numberparsing.h src/haswell/numberparsing.h src/westmere/numberparsing.h src/arm64/intrinsics.h src/haswell/intrinsics.h src/westmere/intrinsics.h src/jsoncharutils.h src/arm64/bitmask.h src/arm64/simd.h src/arm64/stage1_find_marks.h src/arm64/stage2_build_tape.h src/arm64/stringparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/haswell/bitmask.h src/haswell/simd.h src/generic/utf8_fastvalidate_algorithm.h src/generic/utf8_lookup_algorithm.h src/generic/utf8_range_algorithm.h src/generic/utf8_zwegner_algorithm.h src/haswell/stage1_find_marks.h src/haswell/stage2_build_tape.h src/haswell/stringparsing.h src/westmere/bitmask.h src/westmere/simd.h src/westmere/stage1_find_marks.h src/westmere/stage2_build_tape.h src/westmere/stringparsing.h src/generic/stage2_streaming_build_tape.h
67+
LIBHEADERS_GENERIC=src/generic/numberparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/generic/stage2_streaming_build_tape.h src/generic/utf8_fastvalidate_algorithm.h src/generic/utf8_lookup_algorithm.h src/generic/utf8_lookup2_algorithm.h src/generic/utf8_range_algorithm.h src/generic/utf8_zwegner_algorithm.h
68+
LIBHEADERS_ARM64= src/arm64/bitmanipulation.h src/arm64/bitmask.h src/arm64/intrinsics.h src/arm64/numberparsing.h src/arm64/simd.h src/arm64/stage1_find_marks.h src/arm64/stage2_build_tape.h src/arm64/stringparsing.h
69+
LIBHEADERS_HASWELL= src/haswell/bitmanipulation.h src/haswell/bitmask.h src/haswell/intrinsics.h src/haswell/numberparsing.h src/haswell/simd.h src/haswell/stage1_find_marks.h src/haswell/stage2_build_tape.h src/haswell/stringparsing.h
70+
LIBHEADERS_WESTMERE=src/westmere/bitmanipulation.h src/westmere/bitmask.h src/westmere/intrinsics.h src/westmere/numberparsing.h src/westmere/simd.h src/westmere/stage1_find_marks.h src/westmere/stage2_build_tape.h src/westmere/stringparsing.h
71+
LIBHEADERS=src/jsoncharutils.h src/simdprune_tables.h $(LIBHEADERS_GENERIC) $(LIBHEADERS_ARM64) $(LIBHEADERS_HASWELL) $(LIBHEADERS_WESTMERE)
72+
6873
PUBHEADERS=include/simdjson/common_defs.h include/simdjson/isadetection.h include/simdjson/jsonformatutils.h include/simdjson/jsonioutil.h include/simdjson/jsonminifier.h include/simdjson/jsonparser.h include/simdjson/padded_string.h include/simdjson/parsedjson.h include/simdjson/parsedjsoniterator.h include/simdjson/portability.h include/simdjson/simdjson.h include/simdjson/simdjson_version.h include/simdjson/stage1_find_marks.h include/simdjson/stage2_build_tape.h
6974
HEADERS=$(PUBHEADERS) $(LIBHEADERS)
7075

‎scripts/shootout.sh‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
function report_perf() {
2+
algorithm=$1
3+
architecture=$2
4+
iterations=$3
5+
for run in {1..2}
6+
do
7+
echo -n "| $architecture | $algorithm "
8+
for file in "${@:4}"
9+
do
10+
./parse -f $EXTRAARGS -n $iterations jsonexamples/$file.json | grep "stage 1 instructions" | sed -E "s/^.*stage 1 instructions:\s*([0-9]+)\s+cycles:\s*([0-9]+).+mis. branches:\s*([0-9]+).*/| \2 | \1 | \3 /" | tr -d "\n"
11+
done
12+
echo "|"
13+
done
14+
}
15+
echo -n "| Architecture | Algorithm "
16+
for file in "${@:3}"
17+
do
18+
echo -n "| $file Cycles | $file Instructions | $file Missed Branches "
19+
done
20+
echo "|"
21+
22+
git checkout jkeiser/lookup2_simpler_intel
23+
make parse
24+
report_perf lookup2 "$@"
25+
26+
git checkout jkeiser/lookup2
27+
make parse
28+
report_perf lookup2_old "$@"
29+
30+
git checkout master
31+
make parse
32+
report_perf fastvalidate "$@"

‎src/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ set(SIMDJSON_SRC_HEADERS
5252
generic/numberparsing.h
5353
generic/utf8_fastvalidate_algorithm.h
5454
generic/utf8_lookup_algorithm.h
55+
generic/utf8_lookup2_algorithm.h
5556
generic/utf8_range_algorithm.h
5657
generic/utf8_zwegner_algorithm.h
5758
haswell/bitmask.h

‎src/arm64/simd.h‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -120,15 +120,22 @@ namespace simdjson::arm64::simd {
120120
really_inline simd8<uint8_t>& operator-=(const simd8<uint8_t> other) { *this = *this - other; return *this; }
121121

122122
// Order-specific operations
123+
really_inline uint8_t max() const { return vmaxvq_u8(*this); }
124+
really_inline uint8_t min() const { return vminvq_u8(*this); }
123125
really_inline simd8<uint8_t> max(const simd8<uint8_t> other) const { return vmaxq_u8(*this, other); }
124126
really_inline simd8<uint8_t> min(const simd8<uint8_t> other) const { return vminq_u8(*this, other); }
125127
really_inline simd8<bool> operator<=(const simd8<uint8_t> other) const { return vcleq_u8(*this, other); }
126128
really_inline simd8<bool> operator>=(const simd8<uint8_t> other) const { return vcgeq_u8(*this, other); }
129+
really_inline simd8<bool> operator<(const simd8<uint8_t> other) const { return vcltq_u8(*this, other); }
127130
really_inline simd8<bool> operator>(const simd8<uint8_t> other) const { return vcgtq_u8(*this, other); }
131+
// Same as >, but instead of guaranteeing all 1's == true, false = 0 and true = nonzero. For ARM, returns all 1's.
132+
really_inline simd8<uint8_t> gt_bits(const simd8<uint8_t> other) const { return simd8<uint8_t>(*this > other); }
133+
// Same as <, but instead of guaranteeing all 1's == true, false = 0 and true = nonzero. For ARM, returns all 1's.
134+
really_inline simd8<uint8_t> lt_bits(const simd8<uint8_t> other) const { return simd8<uint8_t>(*this < other); }
128135

129136
// Bit-specific operations
130137
really_inline simd8<bool> any_bits_set(simd8<uint8_t> bits) const { return vtstq_u8(*this, bits); }
131-
really_inline bool any_bits_set_anywhere() const { return vmaxvq_u8(*this) != 0; }
138+
really_inline bool any_bits_set_anywhere() const { return this->max() != 0; }
132139
really_inline bool any_bits_set_anywhere(simd8<uint8_t> bits) const { return (*this & bits).any_bits_set_anywhere(); }
133140
template<int N>
134141
really_inline simd8<uint8_t> shr() const { return vshrq_n_u8(*this, N); }
@@ -216,6 +223,7 @@ namespace simdjson::arm64::simd {
216223
really_inline simd8<int8_t> max(const simd8<int8_t> other) const { return vmaxq_s8(*this, other); }
217224
really_inline simd8<int8_t> min(const simd8<int8_t> other) const { return vminq_s8(*this, other); }
218225
really_inline simd8<bool> operator>(const simd8<int8_t> other) const { return vcgtq_s8(*this, other); }
226+
really_inline simd8<bool> operator<(const simd8<int8_t> other) const { return vcltq_s8(*this, other); }
219227
really_inline simd8<bool> operator==(const simd8<int8_t> other) const { return vceqq_s8(*this, other); }
220228

221229
template<int N=1>

‎src/arm64/stage1_find_marks.h‎

Lines changed: 18 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,24 @@ really_inline void find_whitespace_and_operators(
3030
whitespace = v.map([&](simd8<uint8_t> _v) { return _v.any_bits_set(0x18); }).to_bitmask();
3131
}
3232

33-
#include "generic/utf8_fastvalidate_algorithm.h"
33+
really_inline bool is_ascii(simd8x64<uint8_t> input) {
34+
simd8<uint8_t> bits = input.reduce([&](auto a,auto b) { return a|b; });
35+
return bits.max() < 0b10000000u;
36+
}
37+
38+
really_inline simd8<bool> must_be_continuation(simd8<uint8_t> prev1, simd8<uint8_t> prev2, simd8<uint8_t> prev3) {
39+
simd8<bool> is_second_byte = prev1 >= uint8_t(0b11000000u);
40+
simd8<bool> is_third_byte = prev2 >= uint8_t(0b11100000u);
41+
simd8<bool> is_fourth_byte = prev3 >= uint8_t(0b11110000u);
42+
// Use ^ instead of | for is_*_byte, because ^ is commutative, and the caller is using ^ as well.
43+
// This will work fine because we only have to report errors for cases with 0-1 lead bytes.
44+
// Multiple lead bytes implies 2 overlapping multibyte characters, and if that happens, there is
45+
// guaranteed to be at least *one* lead byte that is part of only 1 other multibyte character.
46+
// The error will be detected there.
47+
return is_second_byte ^ is_third_byte ^ is_fourth_byte;
48+
}
49+
50+
#include "generic/utf8_lookup2_algorithm.h"
3451
#include "generic/stage1_find_marks.h"
3552

3653
} // namespace simdjson::arm64

0 commit comments

Comments
 (0)