You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@fury.apache.org by "pandalee99 (via GitHub)" <gi...@apache.org> on 2024/07/03 08:06:39 UTC

[PR] feat(C++): String detection is performed using SIMD techniques [fury]

pandalee99 opened a new pull request, #1720:
URL: https://github.com/apache/fury/pull/1720

   ## What does this PR do?
   ref: https://arxiv.org/pdf/1902.08318.pdf
   ref: https://github.com/simdutf/simdutf
   I learned about the related simd technology, as well as this paper and project implementation.
   Using SIMD technique for string detection.
   First, I need to implement the logic and complete the latin character detection
   ``` c++
   // Baseline implementation
   bool isLatin_Baseline(const std::string& str) {
       for (char c : str) {
           if (static_cast<unsigned char>(c) >= 128) {
               return false;
           }
       }
       return true;
   }
   ```
   <img width="393" alt="image" src="https://raw.githubusercontent.com/pandalee99/image_store/master/hexo/simd_base_line_test1.png">
   Then, I tried to use SSE2 to speed it up, which is obviously a little bit faster, the logic is to read multiple characters at once and then do the bit arithmetic
   Obviously, there was a speed boost, but I didn't think it was enough, so I tried it again with AVX2
   <img width="493" alt="image" 
   src="https://raw.githubusercontent.com/pandalee99/image_store/master/hexo/simd_test_all_1.png">
   I think in terms of efficiency, it's already much faster than before. 
   But how do you prove that it's also logically true?
   I added test samples to verify
   
   ``` C++
   TEST(StringUtilTest, TestIsLatinLogic)
   ```
   
   Finally, I ran the test
   <img width="493" alt="image" 
   src="https://raw.githubusercontent.com/pandalee99/image_store/master/hexo/simd_ubantu_test_1.png">
   done.
   
   
   <!-- Describe the purpose of this PR. -->
   
   
   ## Related issues
   Closes #313 
   
   <!--
   Is there any related issue? Please attach here.
   
   - #xxxx0
   - #xxxx1
   - #xxxx2
   -->
   
   
   ## Does this PR introduce any user-facing change?
   
   <!--
   If any user-facing interface changes, please [open an issue](https://github.com/apache/fury/issues/new/choose) describing the need to do so and update the document if necessary.
   -->
   
   - [ ] Does this PR introduce any public API change?
   - [ ] Does this PR introduce any binary protocol compatibility change?
   
   
   ## Benchmark
   
   <!--
   When the PR has an impact on performance (if you don't know whether the PR will have an impact on performance, you can submit the PR first, and if it will have impact on performance, the code reviewer will explain it), be sure to attach a benchmark data here.
   -->
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "pandalee99 (via GitHub)" <gi...@apache.org>.
pandalee99 commented on PR #1720:
URL: https://github.com/apache/fury/pull/1720#issuecomment-2214232373

   @chaokunyang can u help me see this problem? 
   <img width="472" alt="image" src="https://github.com/apache/fury/assets/46820719/35f3d685-e6aa-42c9-8ba5-e348450b97d5">
   this seems to be a CI error


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "pandalee99 (via GitHub)" <gi...@apache.org>.
pandalee99 commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1676832015


##########
cpp/fury/util/string_util.h:
##########
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#pragma once
+
+#include <string>
+
+namespace fury {
+
+bool isLatin_Baseline(const std::string &str);
+bool isLatin_AVX2(const std::string &str);
+bool isLatin_SSE2(const std::string &str);
+bool isLatin_NEON(const std::string &str);
+bool isLatin_RISCV(const std::string &str);

Review Comment:
   I get it



##########
cpp/fury/util/string_util.h:
##########
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#pragma once
+
+#include <string>
+
+namespace fury {
+
+bool isLatin_Baseline(const std::string &str);
+bool isLatin_AVX2(const std::string &str);
+bool isLatin_SSE2(const std::string &str);
+bool isLatin_NEON(const std::string &str);
+bool isLatin_RISCV(const std::string &str);
+std::string generateRandomString(size_t length);

Review Comment:
   I get it



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "chaokunyang (via GitHub)" <gi...@apache.org>.
chaokunyang commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1675632470


##########
cpp/fury/util/string_util.h:
##########
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#pragma once
+
+#include <string>
+
+namespace fury {
+
+bool isLatin_Baseline(const std::string &str);
+bool isLatin_AVX2(const std::string &str);
+bool isLatin_SSE2(const std::string &str);
+bool isLatin_NEON(const std::string &str);
+bool isLatin_RISCV(const std::string &str);
+std::string generateRandomString(size_t length);

Review Comment:
   Could we add a method which select implementation based the macro. Otherwise, how do know which method should be invoked?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "pandalee99 (via GitHub)" <gi...@apache.org>.
pandalee99 commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1674388592


##########
cpp/fury/util/string_util_test.cc:
##########
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#include "string_util.h"
+#include <chrono>
+#include <gtest/gtest.h>
+
+namespace fury {
+// TEST efficiency
+TEST(StringUtilTest, TestIsLatinFunctions) {
+  // Generate a unique test string once
+  std::string testStr = generateRandomString(100000);
+  std::cout << "testStr : " << std::endl;
+
+  //  Baseline
+  auto start_time = std::chrono::high_resolution_clock::now();
+  bool result_baseline = isLatin_Baseline(testStr);
+  auto end_time = std::chrono::high_resolution_clock::now();
+  auto duration_baseline = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                               end_time - start_time)
+                               .count();
+  std::cout << "Baseline Running Time: " << duration_baseline << " ns"
+            << std::endl;
+  EXPECT_TRUE(result_baseline);
+
+  //  AVX2
+  start_time = std::chrono::high_resolution_clock::now();
+  bool result_avx2 = isLatin_AVX2(testStr);
+  end_time = std::chrono::high_resolution_clock::now();
+  auto duration_avx2 = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                           end_time - start_time)
+                           .count();
+  std::cout << "AVX2 Running Time: " << duration_avx2 << " ns" << std::endl;
+  EXPECT_TRUE(result_avx2);
+
+  //  SSE2
+  start_time = std::chrono::high_resolution_clock::now();
+  bool result_sse2 = isLatin_SSE2(testStr);
+  end_time = std::chrono::high_resolution_clock::now();
+  auto duration_sse2 = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                           end_time - start_time)
+                           .count();
+  std::cout << "SSE2 Running Time: " << duration_sse2 << " ns" << std::endl;
+  EXPECT_TRUE(result_sse2);
+}
+
+// TEST Logic
+TEST(StringUtilTest, TestIsLatinLogic) {
+
+  EXPECT_TRUE(isLatin_AVX2("Fury"));

Review Comment:
   thanks!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "pandalee99 (via GitHub)" <gi...@apache.org>.
pandalee99 commented on PR #1720:
URL: https://github.com/apache/fury/pull/1720#issuecomment-2226922448

   Of course, we can add benchmark, but the change of this pr is relatively small. If we need to add benchmark, we can build the basic framework in another pr, how about that?
   For this pr I added Fury log to express the increased efficiency.
   <img width="352" alt="image" src="https://github.com/user-attachments/assets/f9207551-1335-414d-8bf1-41ef477d912b">
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "chaokunyang (via GitHub)" <gi...@apache.org>.
chaokunyang merged PR #1720:
URL: https://github.com/apache/fury/pull/1720


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
PragmaTwice commented on PR #1720:
URL: https://github.com/apache/fury/pull/1720#issuecomment-2226790418

   I'm wondering if we can add a benchmark into the codebase via https://github.com/google/benchmark.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "chaokunyang (via GitHub)" <gi...@apache.org>.
chaokunyang commented on PR #1720:
URL: https://github.com/apache/fury/pull/1720#issuecomment-2223046528

   ![image](https://github.com/apache/fury/assets/12445254/6bd35d7a-12d4-44ab-a35f-68e136ff9531)
   Seems this test has an compilation error


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
PragmaTwice commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1676768391


##########
cpp/fury/util/string_util.h:
##########
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#pragma once
+
+#include <string>
+
+namespace fury {
+
+bool isLatin_Baseline(const std::string &str);
+bool isLatin_AVX2(const std::string &str);
+bool isLatin_SSE2(const std::string &str);
+bool isLatin_NEON(const std::string &str);
+bool isLatin_RISCV(const std::string &str);

Review Comment:
   Could we detect the platform automatically and provide a `isLatin` that can select the suitable implementation?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "pandalee99 (via GitHub)" <gi...@apache.org>.
pandalee99 commented on PR #1720:
URL: https://github.com/apache/fury/pull/1720#issuecomment-2212471761

   @chaokunyang can u help me review this pr?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "chaokunyang (via GitHub)" <gi...@apache.org>.
chaokunyang commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1675633455


##########
cpp/fury/util/string_util_test.cc:
##########
@@ -0,0 +1,84 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#include "string_util.h"
+#include <chrono>
+#include <gtest/gtest.h>
+#include <iostream>
+
+namespace fury {
+
+#if defined(__x86_64__) || defined(_M_X64)
+bool isLatin(const std::string &str) { return isLatin_AVX2(str); }

Review Comment:
   this should be moved into string_util.h



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org


Re: [PR] feat(C++): String detection is performed using SIMD techniques [fury]

Posted by "chaokunyang (via GitHub)" <gi...@apache.org>.
chaokunyang commented on code in PR #1720:
URL: https://github.com/apache/fury/pull/1720#discussion_r1674090911


##########
cpp/fury/util/string_util_test.cc:
##########
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#include "string_util.h"
+#include <chrono>
+#include <gtest/gtest.h>
+
+namespace fury {
+// TEST efficiency
+TEST(StringUtilTest, TestIsLatinFunctions) {
+  // Generate a unique test string once
+  std::string testStr = generateRandomString(100000);
+  std::cout << "testStr : " << std::endl;
+
+  //  Baseline
+  auto start_time = std::chrono::high_resolution_clock::now();
+  bool result_baseline = isLatin_Baseline(testStr);
+  auto end_time = std::chrono::high_resolution_clock::now();
+  auto duration_baseline = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                               end_time - start_time)
+                               .count();
+  std::cout << "Baseline Running Time: " << duration_baseline << " ns"
+            << std::endl;
+  EXPECT_TRUE(result_baseline);
+
+  //  AVX2
+  start_time = std::chrono::high_resolution_clock::now();
+  bool result_avx2 = isLatin_AVX2(testStr);
+  end_time = std::chrono::high_resolution_clock::now();
+  auto duration_avx2 = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                           end_time - start_time)
+                           .count();
+  std::cout << "AVX2 Running Time: " << duration_avx2 << " ns" << std::endl;
+  EXPECT_TRUE(result_avx2);
+
+  //  SSE2
+  start_time = std::chrono::high_resolution_clock::now();
+  bool result_sse2 = isLatin_SSE2(testStr);
+  end_time = std::chrono::high_resolution_clock::now();
+  auto duration_sse2 = std::chrono::duration_cast<std::chrono::nanoseconds>(
+                           end_time - start_time)
+                           .count();
+  std::cout << "SSE2 Running Time: " << duration_sse2 << " ns" << std::endl;
+  EXPECT_TRUE(result_sse2);
+}
+
+// TEST Logic
+TEST(StringUtilTest, TestIsLatinLogic) {
+
+  EXPECT_TRUE(isLatin_AVX2("Fury"));

Review Comment:
   AVX2 doesn't exists for ARM based CPU, could we make this work on ARM by using some macro check



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@fury.apache.org
For additional commands, e-mail: commits-help@fury.apache.org