Tôi có .NET và C++ thực hiện chức năng kiểm tra hoàn hảo, thực hiện tra cứu 854,750 trong từ điển bằng các phím chuỗi từ một nhóm 6838 phím. Tôi đã viết những chức năng này để điều tra một nút cổ chai hoàn hảo trong một ứng dụng thực tế.C++ ~ 1M tra cứu trong unordered_map với chuỗi khóa hoạt động chậm hơn nhiều so với mã .NET
.NET thực hiện được viết bằng F #, sử dụng từ điển và được biên soạn cho .NET 4.0
C++ thực hiện sử dụng std :: unordered_map và được xây dựng với VS2010 trong chế độ Release.
Trên máy tính của tôi. Mã .NET chạy trong 240 ms trung bình và mã C++ chạy trong 630 mili giây. Bạn có thể vui lòng giúp tôi hiểu những gì có thể là lý do cho sự khác biệt lớn về tốc độ này?
Nếu tôi thực hiện độ dài khóa trong C++ ngắn hơn và sử dụng tiền tố "key_" thay vì "key_prefix_", nó sẽ chạy trong 140 ms.
Một thủ thuật khác mà tôi đã thử là thay thế std :: string bằng cách triển khai chuỗi không thay đổi tùy chỉnh có con trỏ const char * đến nguồn và băm được tính một lần. Sử dụng chuỗi này cho phép để có được hiệu suất của C++ thực hiện xuống 190 ms.
C++:
struct SomeData
{
public:
float Value;
};
typedef std::string KeyString;
typedef std::unordered_map<KeyString, SomeData> DictionaryT;
const int MaxNumberOfRuns = 125;
const int MaxNumberOfKeys = 6838;
DictionaryT dictionary;
dictionary.rehash(MaxNumberOfKeys);
auto timer = Stopwatch::StartNew();
int lookupCount = 0;
char keyBuffer[100] = "key_prefix_";
size_t keyPrefixLen = std::strlen(keyBuffer);
/// run MaxNumberOfRuns * MaxNumberOfKeys iterations
for(int runId = 0; runId < MaxNumberOfRuns; runId++)
{
for(int keyId = 0; keyId < MaxNumberOfKeys; keyId++)
{
/// get a new key from the pool of MaxNumberOfKeys keys
int randomKeySuffix = (std::rand() % MaxNumberOfKeys);
::itoa(randomKeySuffix, keyBuffer + keyPrefixLen, 10);
KeyString key = keyBuffer;
/// lookup key in the dictionary
auto dataIter = dictionary.find(key);
SomeData* data;
if(dataIter != dictionary.end())
{
/// get existing value
data = &dataIter->second;
}
else
{
/// add a new value
data = &dictionary.insert(dataIter, DictionaryT::value_type(key, SomeData()))->second;
}
/// update corresponding value in the dictionary
data->Value += keyId * runId;
lookupCount++;
}
}
timer.Stop();
std::cout << "Time: " << timer.GetElapsedMilleseconds() << " ms" << std::endl;
std::cout << "Lookup count: " << lookupCount << std::endl;
Prints:
Thời gian: 636 ms
Lookup đếm: 854750
F # mã
open System
open System.Diagnostics
open System.Collections.Generic
type SomeData =
struct
val mutable Value : float
end
let dictionary = new Dictionary<string, SomeData>()
let randomGen = new Random()
let MaxNumberOfRuns = 125
let MaxNumberOfKeys = 6838
let timer = Stopwatch.StartNew()
let mutable lookupCount = 0
/// run MaxNumberOfRuns * MaxNumberOfKeys iterations
for runId in 1 .. MaxNumberOfRuns do
for keyId in 1 .. MaxNumberOfKeys do
/// get a new key from the pool of MaxNumberOfKeys keys
let randomKeySuffix = randomGen.Next(0, MaxNumberOfKeys).ToString()
let key = "key_prefix_" + randomKeySuffix
/// lookup key in the dictionary
let mutable found, someData = dictionary.TryGetValue (key)
if not(found) then
/// add a new value
someData <- new SomeData()
dictionary.[key] <- someData
/// update corresponding value in the dictionary
someData.Value <- someData.Value + float(keyId) * float(runId)
lookupCount <- lookupCount + 1
timer.Stop()
printfn "Time: %d ms" timer.ElapsedMilliseconds
printfn "Lookup count: %d" lookupCount
Prints:
Thời gian: 245 ms
Lookup đếm: 854750
Có lẽ sử dụng trình lặp kết thúc unordered_map vì gợi ý phần tử tiếp theo đang cản trở hiệu suất? – GWW
Cả hai đều chạy từ bộ nhớ cache lạnh hoặc cả từ bộ nhớ cache nóng? – sarnold
Không loại bỏ gợi ý phần tử tiếp theo không giúp: (Cả hai chức năng đều chạy với bộ đệm lạnh. – evgenyp