Table of Contents
Slice expansion
Trigger
Principle
Mechanism
Before V1.8:
V1 After .8:
Map expansion
Home Backend Development Golang What are the expansion methods of go language?

What are the expansion methods of go language?

Jan 16, 2023 pm 04:11 PM
golang go language

Go language expansion methods include: 1. Slice expansion. When using append to add elements to Slice, if the Slice space is insufficient, Slice expansion will be triggered; 2. Map expansion. There are two conditions that trigger Map expansion: 1. When the load factor is greater than 6.5, that is, the average number of key-value pairs stored in each bucket reaches 6.5; 2. When the number of overflows is greater than 2^15, that is, when the number of overflows exceeds 32768.

What are the expansion methods of go language?

The operating environment of this tutorial: Windows 7 system, GO version 1.18, Dell G3 computer.

Slice expansion

Trigger

When using append to append elements to Slice, if the Slice space is insufficient, Slice will be triggered Expansion

Principle

Expansion is actually to reallocate a larger memory, copy the original Slice data into the new Slice, then return to the new Slice, and then append the data to it after expansion .

Mechanism

Before V1.8:

The selection of expansion capacity follows the following rules:

  • If the original Slice capacity is less than 1024 , the new Slice capacity will be expanded to 2 times the original;
  • If the original Slice capacity is greater than or equal to 1024, the new Slice capacity will be expanded to 1.25 times the original;
// 1.17及以前的版本中
// old指切片的旧容量, cap指期望的新容量
func growslice(old, cap int) int {
    newcap := old
    doublecap := newcap + newcap
    // 如果期望容量大于旧容量的2倍,则直接使用期望容量作为最终容量
    if cap > doublecap {
        newcap = cap
    } else {
        // 如果旧容量小于1024,则直接翻倍
        if old < 1024 {
            newcap = doublecap
        } else {
            // 每次增长大约1.25倍
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    // 这里忽略了对齐操作
    return newcap
}
Copy after login

V1 After .8:

The selection of new expansion capacity follows the following rules: (has a smoother expansion coefficient)

  • If the original Slice capacity is less than 256, the new Slice capacity will be expanded to 2 times the original;
  • If the original Slice capacity is greater than or equal to 256, the new Slice capacity will be expanded to the original New capacity = (original capacity 3*256)/4
// 只关心扩容规则的简化版growslice
func growslice(old, cap int) int {
    newcap := old
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256 // 不同点1
        if old < threshold {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += (newcap + 3*threshold) / 4 // 不同点2
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    return newcap
}
Copy after login

Map expansion

There are two conditions for triggering expansion:

  • Load factor> 6.5, that is, the average number of key-value pairs stored in each bucket reaches 6.5. IncrementExpansion

  • ##When the number of overflows > 2^15, that is, when the number of overflows exceeds 32768.

    Equal amountExpansion/rearrangement

  • Note: Creating an overflow bucket does not belong to the expansion mechanism

    Increment Expansion

    • #When the load factor is too large, a new bucket space is opened, and the number of buckets is twice the previous number
    • The new space is referenced by buckets. The old space was referenced by oldbuckets
    • Then the data in oldbuckets will be gradually moved to the newly opened buckets space
    Considering that if the map stores hundreds of millions of keys -value, one-time relocation will cause a relatively large delay. Go adopts a gradual relocation strategy, that is,

    will trigger a relocation every time the map is accessed, and each time 2 key-value pairs will be relocated. After all key-value pairs in oldbuckets have been relocated, delete oldbuckets.

    The following figure shows a map containing a fully loaded bucket (for the convenience of description, the value area of ​​the bucket is omitted in the figure):

    Current map There are 7 key-value pairs stored and only 1 bucket. At this time the load factor is 7 > 6.5. When data is inserted again, the

    capacity expansion operation will be triggered. After capacity expansion, the new insertion key will be written into the new bucket. Note that because the load factor is triggered, the overflow bucket is not created.

    When the 8th key-value pair is inserted,

    capacity expansion will be triggered. The schematic diagram after expansion is as follows:

    Subsequent access operations to the map will trigger migration, and the key-value pairs in the oldbuckets will be gradually relocated.

    The diagram after the migration is completed is as follows:

    # During the data migration process, the key-value pairs in the original bucket will exist in front of the new bucket, and the newly inserted keys The value pair will exist at the end of the new bucket.

    Equal amountExpansion/rearrangement

    The so-called equal amount

    Expansion is not actually an expansion of capacity, the number of buckets No change, redo the relocation action similar to IncrementExpansion, and rearrange the loose key-value pairs to make the bucket usage higher and ensure faster access. In extreme scenarios, such as constant additions and deletions, and key-value pairs are concentrated in a small number of buckets, this will cause the number of overflow buckets to increase, but the load factor is not high, making it impossible to perform incremental migration. , as shown in the figure below:

    As can be seen in the above figure, most of the overflow buckets are empty, and the access efficiency will be very poor. At this time, an equal

    expansion is performed, that is, the number of buckets remains unchanged, and the number of overflow buckets will be reduced after reorganization, which saves space and improves access efficiency.

    【Related recommendations:

    Go video tutorial, Programming teaching

    The above is the detailed content of What are the expansion methods of go language?. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to safely read and write files using Golang? How to safely read and write files using Golang? Jun 06, 2024 pm 05:14 PM

Reading and writing files safely in Go is crucial. Guidelines include: Checking file permissions Closing files using defer Validating file paths Using context timeouts Following these guidelines ensures the security of your data and the robustness of your application.

How to configure connection pool for Golang database connection? How to configure connection pool for Golang database connection? Jun 06, 2024 am 11:21 AM

How to configure connection pooling for Go database connections? Use the DB type in the database/sql package to create a database connection; set MaxOpenConns to control the maximum number of concurrent connections; set MaxIdleConns to set the maximum number of idle connections; set ConnMaxLifetime to control the maximum life cycle of the connection.

Similarities and Differences between Golang and C++ Similarities and Differences between Golang and C++ Jun 05, 2024 pm 06:12 PM

Golang and C++ are garbage collected and manual memory management programming languages ​​respectively, with different syntax and type systems. Golang implements concurrent programming through Goroutine, and C++ implements it through threads. Golang memory management is simple, and C++ has stronger performance. In practical cases, Golang code is simpler and C++ has obvious performance advantages.

How steep is the learning curve of golang framework architecture? How steep is the learning curve of golang framework architecture? Jun 05, 2024 pm 06:59 PM

The learning curve of the Go framework architecture depends on familiarity with the Go language and back-end development and the complexity of the chosen framework: a good understanding of the basics of the Go language. It helps to have backend development experience. Frameworks that differ in complexity lead to differences in learning curves.

How to generate random elements from list in Golang? How to generate random elements from list in Golang? Jun 05, 2024 pm 04:28 PM

How to generate random elements of a list in Golang: use rand.Intn(len(list)) to generate a random integer within the length range of the list; use the integer as an index to get the corresponding element from the list.

Comparison of advantages and disadvantages of golang framework Comparison of advantages and disadvantages of golang framework Jun 05, 2024 pm 09:32 PM

The Go framework stands out due to its high performance and concurrency advantages, but it also has some disadvantages, such as being relatively new, having a small developer ecosystem, and lacking some features. Additionally, rapid changes and learning curves can vary from framework to framework. The Gin framework is a popular choice for building RESTful APIs due to its efficient routing, built-in JSON support, and powerful error handling.

What are the best practices for error handling in Golang framework? What are the best practices for error handling in Golang framework? Jun 05, 2024 pm 10:39 PM

Best practices: Create custom errors using well-defined error types (errors package) Provide more details Log errors appropriately Propagate errors correctly and avoid hiding or suppressing Wrap errors as needed to add context

What are the advantages of golang framework? What are the advantages of golang framework? Jun 06, 2024 am 10:26 AM

Advantages of the Golang Framework Golang is a high-performance, concurrent programming language that is particularly suitable for microservices and distributed systems. The Golang framework makes developing these applications easier by providing a set of ready-made components and tools. Here are some of the key advantages of the Golang framework: 1. High performance and concurrency: Golang itself is known for its high performance and concurrency. It uses goroutines, a lightweight threading mechanism that allows concurrent execution of code, thereby improving application throughput and responsiveness. 2. Modularity and reusability: Golang framework encourages modularity and reusable code. By breaking the application into independent modules, you can easily maintain and update the code

See all articles