memcmp / strcmp与uint64_t比较

Question

memcmp / strcmp与uint64_t比较

c++c++11strcmpmemcmp

3

我有很多长度为8或更短的字符串。

我需要使用memcmp() / strcmp()进行大量比较。

我想知道如果将它们全部转换为std::uint64_t，比较是否会更快。在这种情况下，至少在理论上，比较将是无分支的，也将在单个CPU操作中发生。

有人尝试过类似的东西吗？

这里是一些生成这些数字的测试代码。我假设是小端机器。

我知道如果使用htobe32() / htobe64()，代码可以显着简化。

#include <cstdint>

#include <algorithm>    // std::reverse_copy

namespace rev_impl{
    template<typename T>
    T rev(const char *s){
        T t;
        char *pt = reinterpret_cast<char *>(&t);

        std::reverse_copy(s, s + sizeof(T), pt);

        return t;
    }
}

inline uint32_t rev32(const char *s){
    return rev_impl::rev<uint32_t>(s);
}

inline uint64_t rev64(const char *s){
    return rev_impl::rev<uint64_t>(s);
}


#include <iostream>
#include <iomanip>

template<typename T>
void print_rev(const char *s){
    constexpr auto w = sizeof(T) * 2;

    std::cout << std::setw(w) << std::setfill('.') << std::hex << rev_impl::rev<T>(s) << '\n';
}

inline void print_rev32(const char *s){
    return print_rev<uint32_t>(s);
}

inline void print_rev64(const char *s){
    return print_rev<uint64_t>(s);
}

int main(){
    print_rev64("\0\0\0\0\0\0\0a");
    print_rev64("a\0\0\0\0\0\0\0");

    print_rev32("Niki");
    print_rev32("Nika");
    print_rev32("Nikz");
}

这是测试输出：

..............61
6100000000000000
4e696b69
4e696b61
4e696b7a

- Nick

如果大小小于什么程度，你会如何进行转换？您是否已经为字符串分配了结束填充字符？理论上，您可以使用这种方法，但要注意平台的字节序，不过在您的实现中使用reverse_copy会降低性能收益。 - bipll

如果数据在64位（8字节）边界（地址）上未对齐，则使用uint64_t比较也可能会出现问题。 - Marker

@bipll 左侧补零。 - Nick

@Marker 假设我们将其正确对齐。 - Nick

将8个字节作为一个64位数字进行比较肯定比逐个比较8个字节要快；我曾经为比较大块内存做过类似的事情。你的使用情况更快吗？我想这完全取决于你会有多少零填充和确保所有内容都对齐在64位边界上的开销。 - Marker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- max66 · Answer 1

如果您只需要转换字符串字面量，可以编写以下代码来接受字符数组：

rev

template <typename T, std::size_t N,
          typename = typename std::enable_if<(N<=sizeof(T)+1U)>::type>
constexpr T rev (char const (&arr)[N])
 {
   T ret = 0;

   std::size_t  ui = -1;

   while ( ++ui < N-1U )
      ret <<= CHAR_BIT, ret |= arr[ui];

   while ( ++ui < sizeof(T) )
      ret <<= CHAR_BIT;

   return ret;
 }

请注意，从C++14开始，这个函数可以定义为constexpr，因此您可以编写像这样的代码。

constexpr auto fb = rev<std::uint64_t>("foobar");

以下是您的代码重写为使用字符串字面量：

#include <cstdint>
#include <climits>
#include <iostream>
#include <iomanip>
#include <type_traits>

namespace rev_impl
 {
    template <typename T, std::size_t N,
              typename = typename std::enable_if<(N<=sizeof(T)+1U)>::type>
    T rev (char const (&arr)[N])
     {
       T ret = 0;

       std::size_t  ui = -1;

       while ( ++ui < N-1U )
          ret <<= CHAR_BIT, ret |= arr[ui];

       while ( ++ui < sizeof(T) )
          ret <<= CHAR_BIT;

       return ret;
     }
 }

template <typename T, std::size_t N>
inline uint32_t rev32 (char const (&s)[N])
 { return rev_impl::rev<uint32_t>(s); }

template <typename T, std::size_t N>
inline uint64_t rev64 (char const (&s)[N])
 { return rev_impl::rev<uint64_t>(s); }

template<typename T, std::size_t N>
void print_rev (char const (&s)[N])
 {
   constexpr auto w = sizeof(T) * 2;

   std::cout << std::setw(w) << std::setfill('.') << std::hex
      << rev_impl::rev<T>(s) << '\n';
 }

template <std::size_t N>
inline void print_rev32 (char const (&s)[N])
 { return print_rev<uint32_t>(s); }

template <std::size_t N>
inline void print_rev64 (char const (&s)[N])
 { return print_rev<uint64_t>(s); }

int main ()
 {
   print_rev64("\0\0\0\0\0\0\0a");
   print_rev64("a\0\0\0\0\0\0\0");

   print_rev32("Niki");
   print_rev32("Nika");
   print_rev32("Nikz");
 }