Skip to content

Commit 518e87f

Browse files
authored
[Function][Vectorization] Vectorized ltrim and rtrim function to speedup performance (apache#213)
1 parent 51149a8 commit 518e87f

6 files changed

Lines changed: 202 additions & 59 deletions

File tree

‎be/src/exprs/CMakeLists.txt‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -71,4 +71,5 @@ add_library(Exprs
7171
bitmap_function.cpp
7272
hll_function.cpp
7373
grouping_sets_functions.cpp
74-
topn_function.cpp)
74+
topn_function.cpp
75+
v_string_functions.h)

‎be/src/exprs/string_functions.cpp‎

Lines changed: 4 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
// under the License.
1717

1818
#include "exprs/string_functions.h"
19+
#include "exprs/v_string_functions.h"
1920
#include "util/vectorized-tool/lower.h"
2021
#include "util/vectorized-tool/upper.h"
2122

@@ -387,48 +388,15 @@ StringVal StringFunctions::reverse(FunctionContext* context, const StringVal& st
387388
}
388389

389390
StringVal StringFunctions::trim(FunctionContext* context, const StringVal& str) {
390-
if (str.is_null) {
391-
return StringVal::null();
392-
}
393-
// Find new starting position.
394-
int32_t begin = 0;
395-
while (begin < str.len && str.ptr[begin] == ' ') {
396-
++begin;
397-
}
398-
// Find new ending position.
399-
int32_t end = str.len - 1;
400-
while (end > begin && str.ptr[end] == ' ') {
401-
--end;
402-
}
403-
return StringVal(str.ptr + begin, end - begin + 1);
391+
return VStringFunctions::trim(str);
404392
}
405393

406394
StringVal StringFunctions::ltrim(FunctionContext* context, const StringVal& str) {
407-
if (str.is_null) {
408-
return StringVal::null();
409-
}
410-
// Find new starting position.
411-
int32_t begin = 0;
412-
while (begin < str.len && str.ptr[begin] == ' ') {
413-
++begin;
414-
}
415-
return StringVal(str.ptr + begin, str.len - begin);
395+
return VStringFunctions::ltrim(str);
416396
}
417397

418398
StringVal StringFunctions::rtrim(FunctionContext* context, const StringVal& str) {
419-
if (str.is_null) {
420-
return StringVal::null();
421-
}
422-
if (str.len == 0) {
423-
return str;
424-
}
425-
// Find new ending position.
426-
int32_t end = str.len - 1;
427-
while (end > 0 && str.ptr[end] == ' ') {
428-
--end;
429-
}
430-
DCHECK_GE(end, 0);
431-
return StringVal(str.ptr, (str.ptr[end] == ' ') ? end : end + 1);
399+
return VStringFunctions::rtrim(str);
432400
}
433401

434402
IntVal StringFunctions::ascii(FunctionContext* context, const StringVal& str) {

‎be/src/exprs/v_string_functions.h‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. 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,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#pragma once
19+
20+
#ifndef BE_V_STRING_FUNCTIONS_H
21+
#define BE_V_STRING_FUNCTIONS_H
22+
23+
#include <stdint.h>
24+
#include <unistd.h>
25+
#include "runtime/string_value.hpp"
26+
27+
#ifdef __SSE2__
28+
#include <emmintrin.h>
29+
#endif
30+
31+
#ifdef __SSE4_1__
32+
#include <smmintrin.h>
33+
#endif
34+
35+
namespace doris {
36+
class VStringFunctions {
37+
38+
#ifdef __SSE2__
39+
/// n equals to 16 chars length
40+
static constexpr auto n = sizeof(__m128i);
41+
#endif
42+
public:
43+
static StringVal rtrim(const StringVal& str) {
44+
if (str.is_null || str.len == 0) {
45+
return str;
46+
}
47+
auto begin = 0;
48+
auto end = str.len - 1;
49+
#ifdef __SSE2__
50+
char blank = ' ';
51+
const auto pattern = _mm_set1_epi8(blank);
52+
while (end - begin + 1 >= n) {
53+
const auto v_haystack = _mm_loadu_si128(reinterpret_cast<const __m128i *>(str.ptr + end + 1 - n));
54+
const auto v_against_pattern = _mm_cmpeq_epi8(v_haystack, pattern);
55+
const auto mask = _mm_movemask_epi8(v_against_pattern);
56+
int offset = __builtin_clz(~(mask << n));
57+
/// means not found
58+
if (offset == 0)
59+
{
60+
return StringVal(str.ptr + begin, end - begin + 1);
61+
} else {
62+
end -= offset;
63+
}
64+
}
65+
#endif
66+
while (end >= begin && str.ptr[end] == ' ') {
67+
--end;
68+
}
69+
if (end < 0) {
70+
return StringVal("");
71+
}
72+
return StringVal(str.ptr + begin, end - begin + 1);
73+
}
74+
75+
static StringVal ltrim(const StringVal& str) {
76+
if (str.is_null || str.len == 0) {
77+
return str;
78+
}
79+
auto begin = 0;
80+
auto end = str.len - 1;
81+
#ifdef __SSE2__
82+
char blank = ' ';
83+
const auto pattern = _mm_set1_epi8(blank);
84+
while (end - begin + 1 >= n) {
85+
const auto v_haystack = _mm_loadu_si128(reinterpret_cast<const __m128i *>(str.ptr + begin));
86+
const auto v_against_pattern = _mm_cmpeq_epi8(v_haystack, pattern);
87+
const auto mask = _mm_movemask_epi8(v_against_pattern);
88+
const auto offset = __builtin_ctz(mask ^ 0xffff);
89+
/// means not found
90+
if (offset == 0)
91+
{
92+
return StringVal(str.ptr + begin, end - begin + 1);
93+
} else if (offset > n) {
94+
begin += n;
95+
} else {
96+
begin += offset;
97+
return StringVal(str.ptr + begin, end - begin + 1);
98+
}
99+
}
100+
#endif
101+
while (begin <= end && str.ptr[begin] == ' ') {
102+
++begin;
103+
}
104+
return StringVal(str.ptr + begin, end - begin + 1);
105+
}
106+
107+
static StringVal trim(const StringVal& str) {
108+
if (str.is_null || str.len == 0) {
109+
return str;
110+
}
111+
return rtrim(ltrim(str));
112+
}
113+
};
114+
}
115+
116+
#endif //BE_V_STRING_FUNCTIONS_H

‎be/src/vec/functions/function_string.cpp‎

Lines changed: 5 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@
2424
#include <string_view>
2525

2626
#include "runtime/string_search.hpp"
27+
#include "exprs/v_string_functions.h"
2728
#include "vec/common/pod_array_fwd.h"
2829
#include "vec/functions/function_string_to_string.h"
2930
#include "vec/functions/function_totype.h"
@@ -329,31 +330,17 @@ struct TrimImpl {
329330
ColumnString::Chars& res_data, ColumnString::Offsets& res_offsets) {
330331
size_t offset_size = offsets.size();
331332
res_offsets.resize(offsets.size());
332-
res_data.reserve(data.size());
333333

334334
for (size_t i = 0; i < offset_size; ++i) {
335335
const char* raw_str = reinterpret_cast<const char*>(&data[offsets[i - 1]]);
336-
int str_size = offsets[i] - offsets[i - 1] - 1;
337-
338-
int32_t begin = 0;
336+
StringVal str(raw_str);
339337
if constexpr (is_ltrim) {
340-
while (begin < str_size && raw_str[begin] == ' ') {
341-
++begin;
342-
}
338+
str = VStringFunctions::ltrim(str);
343339
}
344-
345-
int32_t end = str_size - 1;
346340
if constexpr (is_rtrim) {
347-
while (end > begin && raw_str[end] == ' ') {
348-
--end;
349-
}
341+
str = VStringFunctions::rtrim(str);
350342
}
351-
352-
int nstr_size = end - begin + 1;
353-
res_offsets[i] = res_offsets[i - 1] + nstr_size + 1;
354-
res_data.insert_assume_reserved(raw_str + begin, raw_str + begin + nstr_size);
355-
// memcpy(reinterpret_cast<char*>(&res_data[res_offsets[i - 1]]) ,raw_str + begin, nstr_size);
356-
res_data.push_back('0');
343+
StringOP::push_value_string(std::string_view((char*)str.ptr, str.len), i, res_data, res_offsets);
357344
}
358345
return Status::OK();
359346
}

‎be/test/exprs/string_functions_test.cpp‎

Lines changed: 72 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
// under the License.
1717

1818
#include "exprs/string_functions.h"
19+
#include "exprs/v_string_functions.h"
1920

2021
#include <gtest/gtest.h>
2122
#include <iostream>
@@ -124,7 +125,7 @@ TEST_F(StringFunctionsTest, money_format_double) {
124125
result = StringFunctions::money_format(context, doris_udf::DoubleVal(-36854775807.039));
125126
expected = AnyValUtil::from_string(ctx, std::string("-36,854,775,807.04"));
126127
ASSERT_EQ(expected, result);
127-
128+
128129
delete context;
129130
}
130131

@@ -665,6 +666,76 @@ TEST_F(StringFunctionsTest, upper) {
665666
ASSERT_EQ(StringVal(""), StringFunctions::upper(ctx, StringVal("")));
666667
}
667668

669+
TEST_F(StringFunctionsTest, ltrim) {
670+
// no blank
671+
StringVal src("hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
672+
StringVal res = VStringFunctions::ltrim(src);
673+
ASSERT_EQ(src, res);
674+
// empty string
675+
StringVal src1("");
676+
res = VStringFunctions::ltrim(src1);
677+
ASSERT_EQ(src1, res);
678+
// null string
679+
StringVal src2(StringVal::null());
680+
res = VStringFunctions::ltrim(src2);
681+
ASSERT_EQ(src2, res);
682+
// less than 16 blanks
683+
StringVal src3(" hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
684+
res = VStringFunctions::ltrim(src3);
685+
ASSERT_EQ(src, res);
686+
// more than 16 blanks
687+
StringVal src4(" hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
688+
res = VStringFunctions::ltrim(src4);
689+
ASSERT_EQ(src, res);
690+
// all are blanks, less than 16 blanks
691+
StringVal src5(" ");
692+
res = VStringFunctions::ltrim(src5);
693+
ASSERT_EQ(StringVal(""), res);
694+
// all are blanks, more than 16 blanks
695+
StringVal src6(" ");
696+
res = VStringFunctions::ltrim(src6);
697+
ASSERT_EQ(StringVal(""), res);
698+
// src less than 16 length
699+
StringVal src7(" 12345678910");
700+
res = VStringFunctions::ltrim(src7);
701+
ASSERT_EQ(StringVal("12345678910"), res);
702+
}
703+
704+
TEST_F(StringFunctionsTest, rtrim) {
705+
// no blank
706+
StringVal src("hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
707+
StringVal res = VStringFunctions::rtrim(src);
708+
ASSERT_EQ(src, res);
709+
// empty string
710+
StringVal src1("");
711+
res = VStringFunctions::rtrim(src1);
712+
ASSERT_EQ(src1, res);
713+
// null string
714+
StringVal src2(StringVal::null());
715+
res = VStringFunctions::rtrim(src2);
716+
ASSERT_EQ(src2, res);
717+
// less than 16 blanks
718+
StringVal src3("hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ");
719+
res = VStringFunctions::rtrim(src3);
720+
ASSERT_EQ(src, res);
721+
// more than 16 blanks
722+
StringVal src4("hello worldaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ");
723+
res = VStringFunctions::rtrim(src4);
724+
ASSERT_EQ(src, res);
725+
// all are blanks, less than 16 blanks
726+
StringVal src5(" ");
727+
res = VStringFunctions::rtrim(src5);
728+
ASSERT_EQ(StringVal(""), res);
729+
// all are blanks, more than 16 blanks
730+
StringVal src6(" ");
731+
res = VStringFunctions::rtrim(src6);
732+
ASSERT_EQ(StringVal(""), res);
733+
// src less than 16 length
734+
StringVal src7("12345678910 ");
735+
res = VStringFunctions::rtrim(src7);
736+
ASSERT_EQ(StringVal("12345678910"), res);
737+
}
738+
668739
} // namespace doris
669740

670741
int main(int argc, char** argv) {

‎be/test/vec/function/function_string_test.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,7 @@ TEST(function_string_test, function_string_upper_test) {
107107

108108
vectorized::check_function<vectorized::DataTypeString, true>(func_name, input_types, data_set);
109109
}
110+
110111
TEST(function_string_test, function_string_trim_test) {
111112
std::string func_name = "trim";
112113
std::vector<std::any> input_types = {TypeIndex::String};
@@ -126,17 +127,16 @@ TEST(function_string_test, function_string_ltrim_test) {
126127
DataSet data_set = {{{std::string("a sd")}, std::string("a sd")},
127128
{{std::string(" hello 123 ")}, std::string("hello 123 ")},
128129
{{std::string(" HELLO,!^%")}, std::string("HELLO,!^%")},
129-
{{std::string(" MY test Str你好 ")}, std::string("MY test Str你好 ")},
130+
{{std::string(" 你好MY test Str你好 ")}, std::string("你好MY test Str你好 ")},
130131
{{std::string("")}, std::string("")}};
131-
132132
vectorized::check_function<vectorized::DataTypeString, true>(func_name, input_types, data_set);
133133
}
134134

135135
TEST(function_string_test, function_string_rtrim_test) {
136136
std::string func_name = "rtrim";
137137
std::vector<std::any> input_types = {TypeIndex::String};
138138
DataSet data_set = {{{std::string("a sd ")}, std::string("a sd")},
139-
{{std::string(" hello 123 ")}, std::string(" hello 123")},
139+
{{std::string("hello 123 ")}, std::string("hello 123")},
140140
{{std::string(" HELLO,!^%")}, std::string(" HELLO,!^%")},
141141
{{std::string(" MY test Str你好 ")}, std::string(" MY test Str你好")},
142142
{{std::string("")}, std::string("")}};

0 commit comments

Comments
 (0)