Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to understand multicore search". Friends who are interested might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to understand multicore search".

In CDHashArray, inserting and deleting arrays are sequential operations, and lookups are similar to serialization operations, which seem slow. In fact, for small arrays, such as only a few or a dozen arrays, the efficiency is not slow, which makes the array sequential search which can not be used for large search in the single-core era can get a good application prospect in the multi-core era.

The basic idea of two-level search structure

To understand the design of multi-level data structure, we must first know the basic design idea of two-level search data structure.

The second-level search structure is to find the location of the second-level subtable in the first-level search, and then make a second search in the found second-level subtable to find the corresponding target data.

A typical secondary lookup structure is as follows:

Figure 16.2.1: schematic diagram of secondary search structure

The secondary lookup structure consists of a primary lookup table and a secondary subtable. Each node in a lookup table points to a secondary lookup subtable. When searching, we first map the keywords to the location of the first-level look-up table, then take out the second-level sub-table of the corresponding position, and find the corresponding search target data in the sub-table.

In Intel Threading Building Blocks (TBB) open source projects, concurrent_hash_map uses the simplest secondary lookup structure. It uses a hash table data structure and sets a lock for each bucket of the hash table.

For ordinary search, this simple two-level search structure may be enough, but for some large-scale search, this simple two-level search structure is not enough. The first problem is that if there are too many child tables, the number of locks is also very large, and the locks themselves require a lot of memory overhead.

If the number of fruit tables is too small, it will give rise to another important problem, that is, load balancing. Because in this case, it is possible that the amount of data in each secondary subtable varies greatly, which will result in a small number of visits to some subtables and a large number of visits to some subtables. These tables with high access volume are prone to be accessed by multiple threads at the same time, which leads to centralized lock contention.

In order to solve the shortcomings of the two-level search structure, let's take a look at the design idea of the multi-level search structure.

Design idea of multi-level search structure

The multi-level lookup structure is designed on the basis of the two-level lookup structure. when there are too many data in a child table, it can be divided into two or more sub-tables, and a new index table can be created to point to these split sub-tables. the pointer to the original child table points to the new index table.

If too much data is inserted in the split child table, you can continue to split it, which will form a multi-level lookup data structure.

At this point, I believe you have a deeper understanding of "how to understand multi-core search". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.