Какой алгоритм использует garbage collector в golang

A Guide to the Go Garbage Collector

This guide is intended to aid advanced Go users in better understanding their application costs by providing insights into the Go garbage collector. It also provides guidance on how Go users may use these insights to improve their applications’ resource utilization. It does not assume any knowledge of garbage collection, but does assume familiarity with the Go programming language.

The Go language takes responsibility for arranging the storage of Go values; in most cases, a Go developer need not care about where these values are stored, or why, if at all. In practice, however, these values often need to be stored in computer physical memory and physical memory is a finite resource. Because it is finite, memory must be managed carefully and recycled in order to avoid running out of it while executing a Go program. It’s the job of a Go implementation to allocate and recycle memory as needed.

Another term for automatically recycling memory is garbage collection. At a high level, a garbage collector (or GC, for short) is a system that recycles memory on behalf of the application by identifying which parts of memory are no longer needed. The Go standard toolchain provides a runtime library that ships with every application, and this runtime library includes a garbage collector.

Note that the existence of a garbage collector as described by this guide is not guaranteed by the Go specification, only that the underlying storage for Go values is managed by the language itself. This omission is intentional and enables the use of radically different memory management techniques.

Therefore, this guide is about a specific implementation of the Go programming language and may not apply to other implementations. Specifically, this following guide applies to the standard toolchain (the gc Go compiler and tools). Gccgo and Gollvm both use a very similar GC implementation so many of the same concepts apply, but details may vary.

Furthermore, this is a living document and will change over time to best reflect the latest release of Go. This document currently describes the garbage collector as of Go 1.19.

Where Go Values Live

Before we dive into the GC, let’s first discuss the memory that doesn’t need to be managed by the GC.

For instance, non-pointer Go values stored in local variables will likely not be managed by the Go GC at all, and Go will instead arrange for memory to be allocated that’s tied to the lexical scope in which it’s created. In general, this is more efficient than relying on the GC, because the Go compiler is able to predetermine when that memory may be freed and emit machine instructions that clean up. Typically, we refer to allocating memory for Go values this way as «stack allocation,» because the space is stored on the goroutine stack.

Go values whose memory cannot be allocated this way, because the Go compiler cannot determine its lifetime, are said to escape to the heap. «The heap» can be thought of as a catch-all for memory allocation, for when Go values need to be placed somewhere. The act of allocating memory on the heap is typically referred to as «dynamic memory allocation» because both the compiler and the runtime can make very few assumptions as to how this memory is used and when it can be cleaned up. That’s where a GC comes in: it’s a system that specifically identifies and cleans up dynamic memory allocations.

There are many reasons why a Go value might need to escape to the heap. One reason could be that its size is dynamically determined. Consider for instance the backing array of a slice whose initial size is determined by a variable, rather than a constant. Note that escaping to the heap must also be transitive: if a reference to a Go value is written into another Go value that has already been determined to escape, that value must also escape.

Whether a Go value escapes or not is a function of the context in which it is used and the Go compiler’s escape analysis algorithm. It would be fragile and difficult to try to enumerate precisely when values escape: the algorithm itself is fairly sophisticated and changes between Go releases. For more details on how to identify which values escape and which do not, see the section on eliminating heap allocations.

Tracing Garbage Collection

Garbage collection may refer to many different methods of automatically recycling memory; for example, reference counting. In the context of this document, garbage collection refers to tracing garbage collection, which identifies in-use, so-called live, objects by following pointers transitively.

Let’s define these terms more rigorously.

• Object—An object is a dynamically allocated piece of memory that contains one or more Go values.
• Pointer—A memory address that references any value within an object. This naturally includes Go values of the form *T , but also includes parts of built-in Go values. Strings, slices, channels, maps, and interface values all contain memory addresses that the GC must trace.

Together, objects and pointers to other objects form the object graph. To identify live memory, the GC walks the object graph starting at the program’s roots, pointers that identify objects that are definitely in-use by the program. Two examples of roots are local variables and global variables. The process of walking the object graph is referred to as scanning.

This basic algorithm is common to all tracing GCs. Where tracing GCs differ is what they do once they discover memory is live. Go’s GC uses the mark-sweep technique, which means that in order to keep track of its progress, the GC also marks the values it encounters as live. Once tracing is complete, the GC then walks over all memory in the heap and makes all memory that is not marked available for allocation. This process is called sweeping.

One alternative technique you may be familiar with is to actually move the objects to a new part of memory and leave behind a forwarding pointer that is later used to update all the application’s pointers. We call a GC that moves objects in this way a moving GC; Go has a non-moving GC.

The GC cycle

Because the Go GC is a mark-sweep GC, it broadly operates in two phases: the mark phase, and the sweep phase. While this statement might seem tautological, it contains an important insight: it’s not possible to release memory back to be allocated until all memory has been traced, because there may still be an un-scanned pointer keeping an object alive. As a result, the act of sweeping must be entirely separated from the act of marking. Furthermore, the GC may also not be active at all, when there’s no GC-related work to do. The GC continuously rotates through these three phases of sweeping, off, and marking in what’s known as the GC cycle. For the purposes of this document, consider the GC cycle starting with sweeping, turning off, then marking.

The next few sections will focus on building intuition for the costs of the GC to aid users in tweaking GC parameters for their own benefit.

Understanding costs

The GC is inherently a complex piece of software built on even more complex systems. It’s easy to become mired in detail when trying to understand the GC and tweak its behavior. This section is intended to provide a framework for reasoning about the cost of the Go GC and tuning parameters.

To begin with, consider this model of GC cost based on three simple axioms.

1. The GC involves only two resources: CPU time, and physical memory.
2. The GC’s memory costs consist of live heap memory, new heap memory allocated before the mark phase, and space for metadata that, even if proportional to the previous costs, are small in comparison. Note: live heap memory is memory that was determined to be live by the previous GC cycle, while new heap memory is any memory allocated in the current cycle, which may or may not be live by the end.
3. The GC’s CPU costs are modeled as a fixed cost per cycle, and a marginal cost that scales proportionally with the size of the live heap. Note: Asymptotically speaking, sweeping scales worse than marking and scanning, as it must perform work proportional to the size of the whole heap, including memory that is determined to be not live (i.e. «dead»). However, in the current implementation sweeping is so much faster than marking and scanning that its associated costs can be ignored in this discussion.

This model is simple but effective: it accurately categorizes the dominant costs of the GC. However, this model says nothing about the magnitude of these costs, nor how they interact. To model that, consider the following situation, referred to from here on as the steady-state.

• The rate at which the application allocates new memory (in bytes per second) is constant. Note: it’s important to understand that this allocation rate is completely separate from whether or not this new memory is live. None of it could be live, all of it could be live, or some of it could be live. (On top of this, some old heap memory could also die, so it’s not necessarily the case that if that memory is live, the live heap size grows.)To put this more concretely, consider a web service that allocates 2 MiB of total heap memory for each request that it handles. During the request, at most 512 KiB of that 2 MiB stays live while the request is in flight, and when the service is finished handling the request, all that memory dies. Now, for the sake of simplicity suppose each request takes about 1 second to handle end-to-end. Then, a steady stream of requests, say 100 requests per second, results in an allocation rate of 200 MiB/s and a 50 MiB peak live heap.
• The application’s object graph looks roughly the same each time (objects are similarly sized, there’s a roughly constant number of pointers, the maximum depth of the graph is roughly constant). Another way to think about this is that the marginal costs of GC are constant.

Note: the steady-state may seem contrived, but it’s representative of the behavior of an application under some constant workload. Naturally, workloads can change even while an application is executing, but typically application behavior looks like a bunch of these steady-states strung together with some transient behavior in between.

Note: the steady-state makes no assumptions about the live heap. It may be growing with each subsequent GC cycle, it may shrink, or it may stay the same. However, trying to encompass all of these situations in the explanations to follow is tedious and not very illustrative, so the guide will focus on examples where the live heap remains constant. The GOGC section explores the non-constant live heap scenario in some more detail.

In the steady-state while the live heap size is constant, every GC cycle is going to look identical in the cost model as long as the GC executes after the same amount of time has passed. That’s because in that fixed amount of time, with a fixed rate of allocation by the application, a fixed amount of new heap memory will be allocated. So with the live heap size constant, and that new heap memory constant, memory use is always going to be the same. And because the live heap is the same size, the marginal GC CPU costs will be the same, and the fixed costs will be incurred at some regular interval.

Now consider if the GC were to shift the point at which it runs later in time. Then, more memory would be allocated but each GC cycle would still incur the same CPU cost. However over some other fixed window of time fewer GC cycles would finish, resulting in a lower overall CPU cost. The opposite would be true if the GC decided to start earlier in time: less memory would be allocated and CPU costs would be incurred more often.

This situation represents the fundamental trade-off between CPU time and memory that a GC can make, controlled by how often the GC actually executes. In other words, the trade-off is entirely defined by GC frequency.

One more detail remains to be defined, and that’s when the GC should decide to start. Note that this directly sets the GC frequency in any particular steady-state, defining the trade-off. In Go, deciding when the GC should start is the main parameter which the user has control over.

GOGC

At a high level, GOGC determines the trade-off between GC CPU and memory.

It works by determining the target heap size after each GC cycle, a target value for the total heap size in the next cycle. The GC’s goal is to finish a collection cycle before the total heap size exceeds the target heap size. Total heap size is defined as the live heap size at the end of the previous cycle, plus any new heap memory allocated by the application since the previous cycle. Meanwhile, target heap memory is defined as:

Target heap memory = Live heap + (Live heap + GC roots) * GOGC / 100

As an example, consider a Go program with a live heap size of 8 MiB, 1 MiB of goroutine stacks, and 1 MiB of pointers in global variables. Then, with a GOGC value of 100, the amount of new memory that will be allocated before the next GC runs will be 10 MiB, or 100% of the 10 MiB of work, for a total heap footprint of 18 MiB. With a GOGC value of 50, then it’ll be 50%, or 5 MiB. With a GOGC value of 200, it’ll be 200%, or 20 MiB.

Note: GOGC includes the root set only as of Go 1.18. Previously, it would only count the live heap. Often, the amount of memory in goroutine stacks is quite small and the live heap size dominates all other sources of GC work, but in cases where programs had hundreds of thousands of goroutines, the GC was making poor judgements.

The heap target controls GC frequency: the bigger the target, the longer the GC can wait to start another mark phase and vice versa. While the precise formula is useful for making estimates, it’s best to think of GOGC in terms of its fundamental purpose: a parameter that picks a point in the GC CPU and memory trade-off. The key takeaway is that doubling GOGC will double heap memory overheads and roughly halve GC CPU cost, and vice versa. (To see a full explanation as to why, see the appendix.)

Note: the target heap size is just a target, and there are several reasons why the GC cycle might not finish right at that target. For one, a large enough heap allocation can simply exceed the target. However, other reasons appear in GC implementations that go beyond the GC model this guide has been using thus far. For some more detail, see the latency section, but the complete details may be found in the additional resources.

GOGC may be configured through either the GOGC environment variable (which all Go programs recognize), or through the SetGCPercent API in the runtime/debug package.

Note that GOGC may also be used to turn off the GC entirely (provided the memory limit does not apply) by setting GOGC=off or calling SetGCPercent(-1) . Conceptually, this setting is equivalent to setting GOGC to a value of infinity, as the amount of new memory before a GC is triggered is unbounded.

To better understand everything we’ve discussed so far, try out the interactive visualization below that is built on the GC cost model discussed earlier. This visualization depicts the execution of some program whose non-GC work takes 10 seconds of CPU time to complete. In the first second it performs some initialization step (growing its live heap) before settling into a steady-state. The application allocates 200 MiB in total, with 20 MiB live at a time. It assumes that the only relevant GC work to complete comes from the live heap, and that (unrealistically) the application uses no additional memory.

Use the slider to adjust the value of GOGC to see how the application responds in terms of total duration and GC overhead. Each GC cycle ends while the new heap drops to zero. The time taken while the new heap drops to zero is the combined time for the mark phase for cycle N, and the sweep phase for the cycle N+1. Note that this visualization (and all the visualizations in this guide) assume the application is paused while the GC executes, so GC CPU costs are fully represented by the time it takes for new heap memory to drop to zero. This is only to make visualization simpler; the same intuition still applies. The X axis shifts to always show the full CPU-time duration of the program. Notice that additional CPU time used by the GC increases the overall duration.

Notice that the GC always incurs some CPU and peak memory overhead. As GOGC increases, CPU overhead decreases, but peak memory increases proportionally to the live heap size. As GOGC decreases, the peak memory requirement decreases at the expense of additional CPU overhead.

Note: the graph displays CPU time, not wall-clock time to complete the program. If the program runs on 1 CPU and fully utilizes its resources, then these are equivalent. A real-world program likely runs on a multi-core system and does not 100% utilize the CPUs at all times. In these cases the wall-time impact of the GC will be lower.

Note: the Go GC has a minimum total heap size of 4 MiB, so if the GOGC-set target is ever below that, it gets rounded up. The visualization reflects this detail.

Here’s another example that’s a little bit more dynamic and realistic. Once again, the application takes 10 CPU-seconds to complete without the GC, but the steady-state allocation rate increases dramatically half-way through, and the live heap size shifts around a bit in the first phase. This example demonstrates how the steady-state might look when the live heap size is actually changing, and how a higher allocation rate leads to more frequent GC cycles.

Memory limit

Until Go 1.19, GOGC was the sole parameter that could be used to modify the GC’s behavior. While it works great as a way to set a trade-off, it doesn’t take into account that available memory is finite. Consider what happens when there’s a transient spike in the live heap size: because the GC will pick a total heap size proportional to that live heap size, GOGC must be configured such for the peak live heap size, even if in the usual case a higher GOGC value provides a better trade-off.

The visualization below demonstrates this transient heap spike situation.

If the example workload is running in a container with a bit over 60 MiB of memory available, then GOGC can’t be increased beyond 100, even though the rest of the GC cycles have the available memory to make use of that extra memory. Furthermore, in some applications, these transient peaks can be rare and hard to predict, leading to occasional, unavoidable, and potentially costly out-of-memory conditions.

That’s why in the 1.19 release, Go added support for setting a runtime memory limit. The memory limit may be configured either via the GOMEMLIMIT environment variable which all Go programs recognize, or through the SetMemoryLimit function available in the runtime/debug package.

This memory limit sets a maximum on the total amount of memory that the Go runtime can use. The specific set of memory included is defined in terms of runtime.MemStats as the expression

or equivalently in terms of the runtime/metrics package,

Because the Go GC has explicit control over how much heap memory it uses, it sets the total heap size based on this memory limit and how much other memory the Go runtime uses.

The visualization below depicts the same single-phase steady-state workload from the GOGC section, but this time with an extra 10 MiB of overhead from the Go runtime and with an adjustable memory limit. Try shifting around both GOGC and the memory limit and see what happens.

Memory Limit

Notice that when the memory limit is lowered below the peak memory that’s determined by GOGC (42 MiB for a GOGC of 100), the GC runs more frequently to keep the peak memory within the limit.

Returning to our previous example of the transient heap spike, by setting a memory limit and turning up GOGC, we can get the best of both worlds: no memory limit breach, and better resource economy. Try out the interactive visualization below.

Memory Limit

Notice that with some values of GOGC and the memory limit, peak memory use stops at whatever the memory limit is, but that the rest of the program’s execution still obeys the total heap size rule set by GOGC.

This observation leads to another interesting detail: even when GOGC is set to off, the memory limit is still respected! In fact, this particular configuration represents a maximization of resource economy because it sets the minimum GC frequency required to maintain some memory limit. In this case, all of the program’s execution has the heap size rise to meet the memory limit.

Now, while the memory limit is clearly a powerful tool, the use of a memory limit does not come without a cost, and certainly doesn’t invalidate the utility of GOGC.

Consider what happens when the live heap grows large enough to bring total memory use close to the memory limit. In the steady-state visualization above, try turning GOGC off and then slowly lowering the memory limit further and further to see what happens. Notice that the total time the application takes will start to grow in an unbounded manner as the GC is constantly executing to maintain an impossible memory limit.

This situation, where the program fails to make reasonable progress due to constant GC cycles, is called thrashing. It’s particularly dangerous because it effectively stalls the program. Even worse, it can happen for exactly the same situation we were trying to avoid with GOGC: a large enough transient heap spike can cause a program to stall indefinitely! Try reducing the memory limit (around 30 MiB or lower) in the transient heap spike visualization and notice how the worst behavior specifically starts with the heap spike.

In many cases, an indefinite stall is worse than an out-of-memory condition, which tends to result in a much faster failure.

For this reason, the memory limit is defined to be soft. The Go runtime makes no guarantees that it will maintain this memory limit under all circumstances; it only promises some reasonable amount of effort. This relaxation of the memory limit is critical to avoiding thrashing behavior, because it gives the GC a way out: let memory use surpass the limit to avoid spending too much time in the GC.

How this works internally is the GC sets an upper limit on the amount of CPU time it can use over some time window (with some hysteresis for very short transient spikes in CPU use). This limit is currently set at roughly 50%, with a 2 * GOMAXPROCS CPU-second window. The consequence of limiting GC CPU time is that the GC’s work is delayed, meanwhile the Go program may continue allocating new heap memory, even beyond the memory limit.

The intuition behind the 50% GC CPU limit is based on the worst-case impact on a program with ample available memory. In the case of a misconfiguration of the memory limit, where it is set too low mistakenly, the program will slow down at most by 2x, because the GC can’t take more than 50% of its CPU time away.

Note: the visualizations on this page do not simulate the GC CPU limit.

Suggested uses

While the memory limit is a powerful tool, and the Go runtime takes steps to mitigate the worst behaviors from misuse, it’s still important to use it thoughtfully. Below is a collection of tidbits of advice about where the memory limit is most useful and applicable, and where it might cause more harm than good.

• Do take advantage of the memory limit when the execution environment of your Go program is entirely within your control, and the Go program is the only program with access to some set of resources (i.e. some kind of memory reservation, like a container memory limit). A good example is the deployment of a web service into containers with a fixed amount of available memory. In this case, a good rule of thumb is to leave an additional 5-10% of headroom to account for memory sources the Go runtime is unaware of.
• Do feel free to adjust the memory limit in real time to adapt to changing conditions. A good example is a cgo program where C libraries temporarily need to use substantially more memory.
• Don’t set GOGC to off with a memory limit if the Go program might share some of its limited memory with other programs, and those programs are generally decoupled from the Go program. Instead, keep the memory limit since it may help to curb undesirable transient behavior, but set GOGC to some smaller, reasonable value for the average case. While it may be tempting to try and «reserve» memory for co-tenant programs, unless the programs are fully synchronized (e.g. the Go program calls some subprocess and blocks while its callee executes), the result will be less reliable as inevitably both programs will need more memory. Letting the Go program use less memory when it doesn’t need it will generate a more reliable result overall. This advice also applies to overcommit situations, where the sum of memory limits of containers running on one machine may exceed the actual physical memory available to the machine.
• Don’t use the memory limit when deploying to an execution environment you don’t control, especially when your program’s memory use is proportional to its inputs. A good example is a CLI tool or a desktop application. Baking a memory limit into the program when it’s unclear what kind of inputs it might be fed, or how much memory might be available on the system can lead to confusing crashes and poor performance. Plus, an advanced end-user can always set a memory limit if they wish.
• Don’t set a memory limit to avoid out-of-memory conditions when a program is already close to its environment’s memory limits. This effectively replaces an out-of-memory risk with a risk of severe application slowdown, which is often not a favorable trade, even with the efforts Go makes to mitigate thrashing. In such a case, it would be much more effective to either increase the environment’s memory limits (and then potentially set a memory limit) or decrease GOGC (which provides a much cleaner trade-off than thrashing-mitigation does).

Latency

The visualizations in this document have modeled the application as paused while the GC is executing. GC implementations do exist that behave this way, and they’re referred to as «stop-the-world» GCs.

The Go GC, however, is not fully stop-the-world and does most of its work concurrently with the application. This is primarily to reduce application latencies. Specifically, the end-to-end duration of a single unit of computation (e.g. a web request). Thus far, this document mainly considered application throughput (e.g. web requests handled per second). Note that each example in the GC cycle section focused on the total CPU duration of an executing program. However, such a duration is far less meaningful for say, a web service. While throughput is still important for a web service (i.e. queries per second), often the latency of each individual request matters even more.

In terms of latency, a stop-the-world GC may require a considerable length of time to execute both its mark and sweep phases, during which the application, and in the context of a web service, any in-flight request, is unable to make further progress. Instead, the Go GC avoids making the length of any global application pauses proportional to the size of the heap, and that the core tracing algorithm is performed while the application is actively executing. (The pauses are more strongly proportional to GOMAXPROCS algorithmically, but most commonly are dominated by the time it takes to stop running goroutines.) Collecting concurrently is not without cost: in practice it often leads to a design with lower throughput than an equivalent stop-the-world garbage collector. However, it’s important to note that lower latency does not inherently mean lower throughput, and the performance of the Go garbage collector has steadily improved over time, in both latency and throughput.

The concurrent nature of Go’s current GC does not invalidate anything discussed in this document so far: none of the statements relied on this design choice. GC frequency is still the primary way the GC trades off between CPU time and memory for throughput, and in fact, it also takes on this role for latency. This is because most of the costs for the GC are incurred while the mark phase is active.

The key takeaway then, is that reducing GC frequency may also lead to latency improvements. This applies not only to reductions in GC frequency from modifying tuning parameters, like increasing GOGC and/or the memory limit, but also applies to the optimizations described in the optimization guide.

However, latency is often more complex to understand than throughput, because it is a product of the moment-to-moment execution of the program and not just an aggregation of costs. As a result, the connection between latency and GC frequency is less direct. Below is a list of possible sources of latency for those inclined to dig deeper.

1. Brief stop-the-world pauses when the GC transitions between the mark and sweep phases,
2. Scheduling delays because the GC takes 25% of CPU resources when in the mark phase,
3. User goroutines assisting the GC in response to a high allocation rate,
4. Pointer writes requiring additional work while the GC is in the mark phase, and
5. Running goroutines must be suspended for their roots to be scanned.

These latency sources are visible in execution traces, except for pointer writes requiring additional work.

Additional resources

While the information presented above is accurate, it lacks the detail to fully understand costs and trade-offs in the Go GC’s design. For more information, see the following additional resources.

• The GC Handbook—An excellent general resource and reference on garbage collector design.
• TCMalloc—Design document for the C/C++ memory allocator TCMalloc, which the Go memory allocator is based on.
• Go 1.5 GC announcement—The blog post announcing the Go 1.5 concurrent GC, which describes the algorithm in more detail.
• Getting to Go—An in-depth presentation about the evolution of Go’s GC design up to 2018.
• Go 1.5 concurrent GC pacing—Design document for determining when to start a concurrent mark phase.
• Smarter scavenging—Design document for revising the way the Go runtime returns memory to the operating system.
• Scalable page allocator—Design document for revising the way the Go runtime manages memory it gets from the operating system.
• GC pacer redesign (Go 1.18)—Design document for revising the algorithm to determine when to start a concurrent mark phase.
• Soft memory limit (Go 1.19)—Design document for the soft memory limit.

A note about virtual memory

This guide has largely focused on the physical memory use of the GC, but a question that comes up regularly is what exactly that means and how it compares to virtual memory (typically presented in programs like top as «VSS»).

Physical memory is memory housed in the actual physical RAM chip in most computers. Virtual memory is an abstraction over physical memory provided by the operating system to isolate programs from one another. It’s also typically acceptable for programs to reserve virtual address space that doesn’t map to any physical addresses at all.

Because virtual memory is just a mapping maintained by the operating system, it is typically very cheap to make large virtual memory reservations that don’t map to physical memory.

The Go runtime generally relies upon this view of the cost of virtual memory in a few ways:

• The Go runtime never deletes virtual memory that it maps. Instead, it uses special operations that most operating systems provide to explicitly release any physical memory resources associated with some virtual memory range. This technique is used explicitly to manage the memory limit and return memory to the operating system that the Go runtime no longer needs. The Go runtime also releases memory it no longer needs continuously in the background. See the additional resources for more information.
• On 32-bit platforms, the Go runtime reserves between 128 MiB and 512 MiB of address space up-front for the heap to limit fragmentation issues.
• The Go runtime uses large virtual memory address space reservations in the implementation of several internal data structures. On 64-bit platforms, these typically have a minimum virtual memory footprint of about 700 MiB. On 32-bit platforms, their footprint is negligible.

As a result, virtual memory metrics such as «VSS» in top are typically not very useful in understanding a Go program’s memory footprint. Instead, focus on «RSS» and similar measurements, which more directly reflect physical memory usage.

Optimization guide

Identifying costs

Before trying to optimize how your Go application interacts with the GC, it’s important to first identify that the GC is a major cost in the first place.

The Go ecosystem provides a number of tools for identifying costs and optimizing Go applications. For a brief overview of these tools, see the guide on diagnostics. Here, we’ll focus on a subset of these tools and a reasonable order to apply them in in order to understand GC impact and behavior.

1. CPU profiles A good place to start is with CPU profiling. CPU profiling provides an overview of where CPU time is spent, though to the untrained eye it may be difficult to identify the magnitude of the role the GC plays in a particular application. Luckily, understanding how the GC fits in mostly boils down to knowing what different functions in the `runtime` package mean. Below is a useful subset of these functions for interpreting CPU profiles. Note: the functions listed below are not leaf functions, so they may not show up in the default the pprof tool provides with the top command. Instead, use the top -cum command or use the list command on these functions directly and focus on the cumulative percent column.
   • runtime.gcBgMarkWorker : Entrypoint to the background mark worker goroutines. Time spent here scales with GC frequency and the complexity and size of the object graph. It represents a baseline for how much time the application spends marking and scanning. Note: Within these goroutines, you will find calls to runtime.gcDrainMarkWorkerDedicated , runtime.gcDrainMarkWorkerFractional , and runtime.gcDrainMarkWorkerIdle , which indicate worker type. In a largely idle Go application, the Go GC is going to use up additional (idle) CPU resources to get its job done faster, which is indicated with the runtime.gcDrainMarkWorkerIdle symbol. As a result, time here may represent a large fraction of CPU samples, which the Go GC believes are free. If the application becomes more active, CPU time in idle workers will drop. One common reason this can happen is if an application runs entirely in one goroutine but GOMAXPROCS is >1.
   • runtime.mallocgc : Entrypoint to the memory allocator for heap memory. A large amount of cumulative time spent here (>15%) typically indicates a lot of memory being allocated.
   • runtime.gcAssistAlloc : Function goroutines enter to yield some of their time to assist the GC with scanning and marking. A large amount of cumulative time spent here (>5%) indicates that the application is likely out-pacing the GC with respect to how fast it’s allocating. It indicates a particularly high degree of impact from the GC, and also represents time the application spend marking and scanning. Note that this is included in the runtime.mallocgc call tree, so it will inflate that as well.
2. Execution traces While CPU profiles are great for identifying where time is spent in aggregate, they’re less useful for indicating performance costs that are more subtle, rare, or related to latency specifically. Execution traces on the other hand provide a rich and deep view into a short window of a Go program’s execution. They contain a variety of events related to the Go GC and specific execution paths can be directly observed, along with how the application might interact with the Go GC. All the GC events tracked are conveniently labeled as such in the trace viewer. See the documentation for the runtime/trace package for how to get started with execution traces.
3. GC traces When all else fails, the Go GC provides a few different specific traces that provide much deeper insights into GC behavior. These traces are always printed directly to STDERR, one line per GC cycle, and are configured through the GODEBUG environment variable that all Go programs recognize. They’re mostly useful for debugging the Go GC itself since they require some familiarity with the specifics of the GC’s implementation, but nonetheless can occasionally be useful to gain a better understanding of GC behavior. The core GC trace is enabled by setting GODEBUG=gctrace=1 . The output produced by this trace is documented in the environment variables section in the documentation for the runtime package. A supplementary GC trace called the «pacer trace» provides even deeper insights and is enabled by setting GODEBUG=gcpacertrace=1 . Interpreting this output requires an understanding of the GC’s «pacer» (see additional resources), which is outside the scope of this guide.

Eliminating heap allocations

One way to reduce costs from the GC is to have the GC manage fewer values to begin with. The techniques described below can produce some of the largest improvements in performance, because as the GOGC section demonstrated, the allocation rate of a Go program is a major factor in GC frequency, the key cost metric used by this guide.

Heap profiling

After identifying that the GC is a source of significant costs, the next step in eliminating heap allocations is to find out where most of them are coming from. For this purpose, memory profiles (really, heap memory profiles) are very useful. Check out the documentation for how to get started with them.

Memory profiles describe where in the program heap allocations come from, identifying them by the stack trace at the point they were allocated. Each memory profile can break down memory in four ways.

• inuse_objects —Breaks down the number of objects that are live.
• inuse_space —Breaks down live objects by how much memory they use in bytes.
• alloc_objects —Breaks down the number of objects that have been allocated since the Go program began executing.
• alloc_space —Breaks down the total amount of memory allocated since the Go program began executing.

Switching between these different views of heap memory may be done with either the -sample_index flag to the pprof tool, or via the sample_index option when the tool is used interactively.

Note: memory profiles by default only sample a subset of heap objects so they will not contain information about every single heap allocation. However, this is sufficient to find hot-spots. To change the sampling rate, see runtime.MemProfileRate .

For the purposes of reducing GC costs, alloc_space is typically the most useful view as it directly corresponds to the allocation rate. This view will indicate allocation hot spots that would provide the most benefit.

Escape analysis

Once candidate heap allocation sites have been identified with the help of heap profiles, how can they be eliminated? The key is to leverage the Go compiler’s escape analysis to have the Go compiler find alternative, and more efficient storage for this memory, for example in the goroutine stack. Luckily, the Go compiler has the ability to describe why it decides to escape a Go value to the heap. With that knowledge, it becomes a matter of reorganizing your source code to change the outcome of the analysis (which is often the hardest part, but outside the scope of this guide).

As for how to access the information from the Go compiler’s escape analysis, the simplest way is through a debug flag supported by the Go compiler that describes all optimizations it applied or did not apply to some package in a text format. This includes whether or not values escape. Try the following command, where [package] is some Go package path.

$ go build -gcflags=-m=3 [package]

This information can also be visualized as an overlay in VS Code. This overlay is configured and enabled in the VS Code Go plugin settings.

1. Set the ui.codelenses setting to include gc_details .
2. Enable the overlay for escape analysis by setting ui.diagnostic.annotations to include escape .

Finally, the Go compiler provides this information in a machine-readable (JSON) format that may be used to build additional custom tooling. For more information on that, see the documentation in the source Go code.

Implementation-specific optimizations

The Go GC is sensitive to the demographics of live memory, because a complex graph of objects and pointers both limits parallelism and generates more work for the GC. As a result, the GC contains a few optimizations for specific common structures. The most directly useful ones for performance optimization are listed below.

Note: Applying the optimizations below may reduce the readability of your code by obscuring intent, and may fail to hold up across Go releases. Prefer to apply these optimizations only in the places they matter most. Such places may be identified by using the tools listed in the section on identifying costs.

• Pointer-free values are segregated from other values. As a result, it may be advantageous to eliminate pointers from data structures that do not strictly need them, as this reduces the cache pressure the GC exerts on the program. As a result, data structures that rely on indices over pointer values, while less well-typed, may perform better. This is only worth doing if it’s clear that the object graph is complex and the GC is spending a lot of time marking and scanning.
• The GC will stop scanning values at the last pointer in the value. As a result, it may be advantageous to group pointer fields in struct-typed values at the beginning of the value. This is only worth doing if it’s clear the application spends a lot of its time marking and scanning. (In theory the compiler can do this automatically, but it is not yet implemented, and struct fields are arranged as written in the source code.)

Furthermore, the GC must interact with nearly every pointer it sees, so using indices into an slice, for example, instead of pointers, can aid in reducing GC costs.

Linux transparent huge pages (THP)

When a program accesses memory, the CPU needs to translate the virtual memory addresses it uses into physical memory addresses that refer to the data it was trying to access. To do this, the CPU consults the «page table,» a data structure that represents the mapping from virtual to physical memory, managed by the operating system. Each entry in the page table represents an indivisible block of physical memory called a page, hence the name.

Transparent huge pages (THP) is a Linux feature that transparently replaces pages of physical memory backing contiguous virtual memory regions with bigger blocks of memory called huge pages. By using bigger blocks, fewer page table entries are needed to represent the same memory region, improving page table lookup times. However, bigger blocks mean more waste if only a small part of the huge page is used by the system.

When running Go programs in production, enabling transparent huge pages on Linux can improve throughput and latency at the cost of additional memory use. Applications with small heaps tend not to benefit from THP and may end up using a substantial amount of additional memory (as high as 50%). However, applications with big heaps (1 GiB or more) tend to benefit quite a bit (up to 10% throughput) without very much additional memory overhead (1-2% or less). Being aware of your THP settings in either case can be helpful, and experimentation is always recommended.

One can enable or disable transparent huge pages in a Linux environment by modifying /sys/kernel/mm/transparent_hugepage/enabled . See the official Linux admin guide for more details. If you choose to have your Linux production environment enable transparent huge pages, we recommend the following additional settings for Go programs.

Set /sys/kernel/mm/transparent_hugepage/defrag to defer or defer+madvise .

Appendix

Additional notes on GOGC

The GOGC section claimed that doubling GOGC doubles heap memory overheads and halves GC CPU costs. To see why, let’s break it down mathematically.

Firstly, the heap target sets a target for the total heap size. This target, however, mainly influences the new heap memory, because the live heap is fundamental to the application.

Target heap memory = Live heap + (Live heap + GC roots) * GOGC / 100

Total heap memory = Live heap + New heap memory

New heap memory = (Live heap + GC roots) * GOGC / 100

From this we can see that doubling GOGC would also double the amount of new heap memory that application will allocate each cycle, which captures heap memory overheads. Note that Live heap + GC roots is an approximation of the amount of memory the GC needs to scan.

Next, let’s look at GC CPU cost. Total cost can be broken down as the cost per cycle, times GC frequency over some time period T.

Total GC CPU cost = (GC CPU cost per cycle) * (GC frequency) * T

GC CPU cost per cycle can be derived from the GC model:

GC CPU cost per cycle = (Live heap + GC roots) * (Cost per byte) + Fixed cost

Note that sweep phase costs are ignored here as mark and scan costs dominate.

The steady-state is defined by a constant allocation rate and a constant cost per byte, so in the steady-state we can derive a GC frequency from this new heap memory:

GC frequency = (Allocation rate) / (New heap memory) = (Allocation rate) / ((Live heap + GC roots) * GOGC / 100)

Putting this together, we get the full equation for the total cost:

Total GC CPU cost = (Allocation rate) / ((Live heap + GC roots) * GOGC / 100) * ((Live heap + GC roots) * (Cost per byte) + Fixed cost) * T

For a sufficiently large heap (which represents most cases), the marginal costs of a GC cycle dominate the fixed costs. This allows for a significant simplification of the total GC CPU cost formula.

Total GC CPU cost = (Allocation rate) / (GOGC / 100) * (Cost per byte) * T

From this simplified formula, we can see that if we double GOGC, we halve total GC CPU cost. (Note that the visualizations in this guide do simulate fixed costs, so the GC CPU overheads reported by them will not exactly halve when GOGC doubles.) Furthermore, GC CPU costs are largely determined by allocation rate and the cost per byte to scan memory. For more information on how to reduce these costs specifically, see the optimization guide.

Note: there exists a discrepancy between the size of the live heap, and the amount of that memory the GC actually needs to scan: the same size live heap but with a different structure will result in a different CPU cost, but the same memory cost, resulting a different trade-off. This is why the structure of the heap is part of the definition of the steady-state. The heap target should arguably only include the scannable live heap as a closer approximation of memory the GC needs to scan, but this leads to degenerate behavior when there’s a very small amount of scannable live heap but the live heap is otherwise large.

Управление памятью

В языке Go управление памятью осуществляется автоматически с помощью сборки мусора (garbage collection), что освобождает разработчика от ручного управления памятью. Вот некоторые ключевые аспекты управления памятью в Go:

Автоматическая сборка мусора

Go использует алгоритм сборки мусора с маркировкой и освобождением (mark-and-sweep). Во время выполнения программы, сборщик мусора анализирует и маркирует все объекты, которые по-прежнему используются, а затем освобождает память, занимаемую неиспользуемыми объектами.

Указатели и выделение памяти

В Go есть возможность работы с указателями, но прямое выделение и освобождение памяти с помощью указателей не поддерживается. Выделение памяти происходит автоматически при создании объектов и освобождение памяти происходит автоматически при сборке мусора.

Устранение утечек памяти

При правильном использовании Go управляет памятью и автоматически освобождает неиспользуемую память. Однако, неправильное использование конструкций, таких как циклы ссылок или долгоживущие объекты, может привести к утечкам памяти. Поэтому важно следить за правильным использованием ресурсов и избегать утечек памяти.

Слайсы (slices)

В Go часто используются слайсы, которые представляют собой динамически изменяемые массивы. Слайсы обеспечивают автоматическую расширяемость и управление памятью. При добавлении элементов в слайс или изменении его размера, Go автоматически управляет памятью, выделяя новый участок памяти и копируя данные при необходимости.

Стек и куча

В языке Go существуют две области памяти, известные как «стек» (stack) и «куча» (heap), которые используются для размещения данных и объектов во время выполнения программы. Вот более подробное описание каждой области:

Стек (Stack):

Стек представляет собой участок памяти, который используется для хранения локальных переменных и контекста вызова функций. Каждый поток выполнения программы имеет свой собственный стек. Когда функция вызывается, данные, такие как аргументы функции, локальные переменные и адрес возврата, сохраняются на вершине стека. Когда функция завершается, эти данные удаляются из стека. Операции в стеке очень быстрые и эффективные. Размер стека ограничен и задается на этапе компиляции.

Куча (Heap):

Куча представляет собой область памяти, которая используется для динамического выделения памяти под объекты и данные, которые не ограничены временем жизни функции. Объекты в куче могут быть доступны из разных частей программы и иметь долгоживущий жизненный цикл. Например, это могут быть структуры данных, объекты классов или слайсы. Управление памятью в куче осуществляется сборщиком мусора, который автоматически определяет, какая память больше не используется и освобождает ее. Куча имеет больший размер, чем стек, и обычно является общей памятью для всей программы.

В целом, Go предоставляет разработчику простой и эффективный механизм управления памятью, освобождая его от выделениея и освобождения памяти вручную, как в низкоуровневых языках программирования. Вместо этого, Go автоматически управляет памятью через сборку мусора и предоставляет высокоуровневые конструкции, такие как слайсы и указатели, для работы с данными. Это позволяет разработчику сосредоточиться на бизнес-логике приложения, а не на управлении памятью.

Escape analysis (эскейп анализ)

Escape analysis (Escape analysis) в языке Go является одной из оптимизаций компилятора, которая позволяет определить, будет ли объект или переменная «выброшена» из локальной области и будет ли использоваться вне нее. Этот анализ позволяет определить, следует ли выделить память для объекта на куче или же можно использовать стек для его хранения. Вот некоторые особенности анализа эскейпа в Go:

Стековое распределение (Stack Allocation)

Escape analysis пытается найти переменные, которые могут быть безопасно распределены на стеке вместо кучи. Это происходит, когда переменная не будет использоваться после выхода из локальной области, например, когда она не передается в другие функции или не сохраняется для использования после возврата из текущей функции.

Кучевое распределение (Heap Allocation)

Если Escape analysis обнаруживает, что переменная будет использоваться за пределами локальной области, то объект или переменная будет выделена на куче. Например, когда переменная передается по указателю или сохраняется в глобальной области, она считается «выброшенной» из локальной области и требует распределения памяти на куче.

Оптимизации аллокаций

Escape analysis позволяет компилятору Go оптимизировать аллокации памяти. Если компилятор обнаруживает, что объект может быть безопасно распределен на стеке, это может привести к повышению производительности, так как стековые аллокации более эффективны и быстрые, чем кучевые аллокации.

Escape analysis в Go выполняется компилятором во время компиляции программы. Разработчику не требуется явно указывать, где распределять объекты на стеке или куче — это определяется автоматически на основе анализа кода и его использования переменных и объектов.Оптимизации, которые происходят благодаря анализу эскейпа, позволяют Go достигать высокой производительности и эффективного использования памяти, освобождая разработчика от необходимости явно управлять памятью.

Как устроен garbage collector в Go 1.9 — Андрей Дроздов (Avito)

Недавно вышел релиз Go 1.9, в нем был обновлен алгоритм сборки мусора. Для того чтобы писать быстрые приложения нужно хорошо понимать как это устроено. В своем докладе я расскажу об алгоритмах сборки мусора и деталях реализации runtime.GC() в Go 1.9 на простых примерах.

AvitoTech

October 14, 2017

More Decks by AvitoTech

Один кликстрим на все бэкенды. Дмитрий Хасанов (Авито)
«Масштабируемая архитектура фронтенда» — Роман Дворнов, Avito
Атомарные SPA — Александр Китов, Альфа-Банк

Моделирование пользовательских предпочтений в мультимодальных данных. Hady W. Lauw, Максим Ткаченко (Singapore Management University)

Кластеризация волатильных объявлений с помощью EM-алгоритма — Василий Лексин (Avito)
«(Не)Безопасность 101» — Григорий Джанелидзе, Mosdroid
«CI процессы в Android разработке Avito», Сергей Пинчук, Avito
Кластеризация волатильных объявлений с помощью EM-алгоритма — Василий Лексин (Avito)
Аналитическое хранилище Avito.ru — от больших к очень большим данным — Артем Данилов (Avito)

Other Decks in Technology

SATySFiの開発についての要望
puripuri2100
Azure OpenAI Service — LLM Application 開発 ハンズオン

dahatake

Gen AI 時代における「サーバーレス」の価値を理解しよう / Value of Serverless with genAI
Findyの開発生産性向上への取り組み ~Findyフロントエンドの場合~
株式会社neoAI会社説明資料
JAWS-UG SRE支部 #7 Security Hubは俺の姑
yamaguchitk333
新卒2年目で行ったreInventを4年たった今振り返る

yoshimi0227

コンテナセキュリティに関するプレイドの事例
Let_s-try-aws-jam.pdf
kadogen_0527
ZOZOTOWNにおける開発生産性向上に関する取り組み / Initiatives to Improve Development Productivity at ZOZOTOWN
はたして我々はコミュニティとどう向き合えばよいのだろうか？

ichimichi

クエリ パフォーマンスが著しく低下した場合の一時的な対処方法

Featured

Designing the Hi-DPI Web
The Cost Of JavaScript in 2023
addyosmani
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
Raft: Consensus for Rubyists
Web Components: a chance to create the future
How To Stay Up To Date on Web Technology
chriscoyier
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
Unsuck your backbone
Code Reviewing Like a Champion
What the flash — Photography Introduction
Thoughts on Productivity

jonyablonski

How to Ace a Technical Interview

Transcript

Как устроен garbage
collector
Андрей Дроздов, 2017

Чем мы занимаемся?
● BuyerX/Поиск
● 35 млн посетителей в месяц (~ ¼ Страны)
● 38 млн активных объявлений
● 1 млн поисковых запросов в минуту
2

О чем я расскажу?
● Теория
● Как теория GC используется в Go
● Hacking
● Выводы
3
Основная идея
4
Основная идея
5
Достижимость
● Корневые объекты
● Объекты, связанные с корневыми
● Достижимые из связанных с корневыми
6

Mark’n’Sweep
● Бит достижимости
● Изначально все, кроме корневых, не размечены
Алгоритм:
● Останавливаем выполнение
● Рекурсивно обходим все объекты и выставляем бит достижимости
● Удаляем все недостижимые объекты
● Продолжаем работу программы
7

Mark’n’Sweep
8
Mark’n’Sweep
9
Mark’n’Sweep
10
Минусы
● Паузы
● Обход Heap полностью
● Фрагментация
12

Как же быть?
Проблема: Паузы в GC
Цель: Пауз не должно быть by design
Стратегия: GC должен работать полностью отдельно
13

Breath First Mark
● Делим все объекты на три группы
● На каждом шаге помечаем все достижимые объекты
как scanned
● В “will be scanned” помечаем все, на что есть ссылки
● При завершении BFS удаляем все, что не в 1 и второй
группе
14

BF Mark. Группы
● Black — исследованные объекты
● Gray — ожидающие исследования объекты
● White — неисследованные объекты
15

BFM Start
16
BFM Scan
17
BFM Sweep
18

Почему это работает?
● Мы знаем про все объекты в памяти
● Все, что не попало в 1 и 2 группы, не используется
● Следовательно: удаляется только мусор
● It works
19

Concurrency и что это ломает?
20
Как это починить?
● Процесс может создать новый объект
● Процесс может поменять указатель
21
Неправильный вариант
22
Правильный вариант
23
Reference Counter
24
Reference Counter
25
GC Generations
26

GC Generations
27
● Разделяем объекты на молодые и
старые
● Сканируем с разными интервалами
каждую группу
● Экономим CPU

Переход от 1.4 к 1.5
29
Переход от 1.4 к 1.5
30
Первая версия concurrent gc
32
Бенчмарк
33
https://github.com/WillSewell/gc-latency-experiment

Go 1.9
● После релиза 1.8 возникли проблемы вызовом GC во время сбора
профилей или memory footprint
● Для этого библиотечные функции runtime.GC, debug.SetGCPercent,
debug.FreeOSMemory были обновлены использованием concurrent GC
● Таким образом спайки в latency во время профилирования приложений в
production были побеждены
mgc.go:1016
34

runtime/mgc*
mgc.go — реализация GC
mgclarge.go — структура данных (https://en.wikipedia.org/wiki/Treap)
mgcmark.go — scanner (marking)
mgcsweep.go — sweeper (sweeping)
mgcsweepbuf.go — buffer/set data structure
mgcwork.go — пул GC
mbarrier.go — реализация write barrier
36

Состояния GC
● GCoff — wb запрещен, проводим sweep в фоне
● GCMark — wb активен, обходим объекты и размечаем
● GCMarkTermination — создаем объекты в черной зоне,
wb активен
mgc.go:272
37

mgc.go. Фаза Sweep termination
● Stop the world
● Достижение GC safe-point
● Завершение всех sweep фаз
● Удаление остатков мусора
mgc.go:1203
38

mgc.go. Фаза mark 1
● Перевод состояния из GCoff в GCMark
● Start the world
● Новые объекты попадают в черную зону
● Обход корневых объектов (стек, глобальные переменные, etc.)
● Обработка задач из working pool, обход серой зоны
● Найденные указатели помещаются в working pool
mgcmark.go:54
39

mgc.go. Фаза mark 2
● Глобальная очередь пуста, локальные очереди еще имеют данные
● Останавливается работа gc worker’ов
● Данные кеша очередей выталкиваются в кеш глобальной очереди
● Работа worker’ов продолжается
● Продолжается обработка задач из working pool
mgc.go:1901
40

mgc.go. Фаза Mark termination
● Главная очередь пуста — запускается mark termination
● Stop the world
● Перевод состояния из GCMark в GCMarkTermination
● Дообработка последних задач из очереди
mgc.go:1458
41

mgc.go. Фаза Sweep
● Перевод состояния из GCMarkTermination в GCoff
● Start the world
● Выполнение sweep в фоне
mgc.go:1985
42

Интервалы включения GC
● Константа GOGC
● GC включается при увеличении использования памяти на $(GOGC)
процентов
mgc.go:201
mgc.go:1151
malloc.go:802
43

Очередь задач GC
44
mgcwork.go:58
Очередь задач GC
45
mgcwork.go:100
mgcwork.go:385
lfstack.go:25

Community pain
● Нет реализации compaction
● Нет реализации поколений
● Не используется весь опыт создания GC
● GC не успевает “разгрести” мусор => STW
● Триггер запуска GC
46

Какой алгоритм использует garbage collector в golang

Привет, Хабр! Это вторая статья цикла, о процессе собеседования Golang разработчика. Первую часть вы можете почитать по ссылочке ниже. Как я писал в предыдущем посте, проходя интервью на позицию Golang разработчика, мне удалось собрать пул вопросов, которыми я хотел бы поделиться с вами. Надеюсь эта информация будет полезна и послужит чек листом при подготовке к интервью.

1. Собеседование Golang разработчика (теоретические вопросы), Часть I
2. Собеседование Golang разработчика (теоретические вопросы), Часть II. Что там с конкурентностью?

Оглавление

1. Темы вопросов, рассмотренные в предыдущей части
2. Конкурентность в Golang
3. Каналы в Golang
4. Контексты в Golang
5. Память в Golang
6. Сборщик мусора в Golang
7. Заключение

Темы вопросов, рассмотренные в предыдущей части

В предыдущей части мы рассмотрели вопросы по следующим темам:

• ООП в Golang;
• Области видимости в Golang;
• Операторы в Golang;
• Strings в Golang;
• Int в Golang;
• Const в Golang;
• Array и slice в Golang;
• Map в Golang;
• Интерфейсы в Golang;
• Инструкция defer.

Конкурентность в Golang

Зачастую начальным вопросом к раскрытию темы конкурентности в Golang является вопрос на общее понимание асинхронности «Что такое асинхронность?»

Вычисления в системе могут идти двумя способами:

• синхронно — это когда код выполняется последовательно;
• асинхронно — это когда операцию мы можем выполнять не дожидаясь результата на месте. Обычно подразумевается, что операция может быть выполнена кем-то на стороне.

«Что такое параллельность?»

Вычисления будут являться параллельным только в том случае, если они выполняются одновременно. Как пример можно привести процесс ремонта в доме. У нас есть несколько мастеров-универсалов, каждый из которых выполняет работы на своем объекте под ключ. При этом производительность мастеров не зависит друг от друга, так как их работа не пересекается.

«Что такое конкурентность?»

Конкурентность обеспечивает выполнение нескольких задач посредством переключения контекста. Конкурентные вычисления реализуются на одном ядре системы. Как пример приведем тот же процесс ремонта, но с другими вводными условиями. Теперь мы имеем один объект, на который привлекаем специалистов разного профиля: по демонтажным работам, электрике, подготовке стен и полов, отделке. При этом у нас часто возникают ситуации, когда хозяин уже в процессе подготовки стен, решает, что вот эта стена ему все же не нужна, и на сцену опять выходят демонтажники. Такой процесс организации работ можно назвать конкурентным, так как наши мастера уступают место друг другу, одновременно клеить обои и ломать стены они не могут.

Важным, более общим вопросом, является «Что такое thread?»

Thread — это реализация виртуальных эмуляций физического процессора. Вычисления на разных thread условно можно назвать параллельными.

«Что такое goroutine?»

Горутина — реализация в Go корутины, блоков кода, которые работают асинхронно. Она объявляется через оператор go перед функцией, вычисления которой необходимо сделать асинхронными. На многоядерной архитектуре выполнение горутин можно осуществлять на разных ядрах процессора. Это сделает эти вычисления параллельными и может сильно ускорить вычисления.

«Какие основные отличия горутины от thread?»

Gorutine

Thread

Управляются рантаймом языка

Управляются процессорным ядром

Более высокоуровневая абстракция, поэтому не зависит от системы

Зависит от системы

Требуют большего количества ресурсов

Асинхронно вытесняющий планировщик

Имеет стэк, который может расти

«Каков минимальный и максимальный вес горутин?»

На этот вопрос, ожидается ответ, не сколько весят все вместе взятые поля в структуре g объекта горутины. Интервьюера интересуют минимальный и максимальный размер стэка горутины. Минимальный (начальный) размер стэка составляет 2 КБ. Максимальный размер стэка горутины зависит от архитектуры системы и равен 1 ГБ для 64-разрядной архитектуры, 250 МБ для 32-разрядной архитектуры.

// The minimum size of stack used by Go code _StackMin = 2048

// Max stack size is 1 GB on 64-bit, 250 MB on 32-bit. // Using decimal instead of binary GB and MB because // they look nicer in the stack overflow failure message. if sys.PtrSize == 8 < maxstacksize = 1000000000 >else

«Что будет если размер горутины превысил допустимый максимум?»

Если размер стэка горутины превышен (к примеру запустили бесконечную рекурсию), то приложение упадет с fatal error .

runtime: goroutine stack exceeds 1000000000-byte limit fatal error: stack overflow

«Какое максимальное количество горутин может быть запущено в системе?»

Количество горутин ограничено только оперативной памятью системы.

«Что такое планировщик go?»

Управление горутинами осуществляет Go планировщик. Про тонкости работы планировщика можно рассказывать бесконечно долго, поэтому сосредоточимся на основных моментах. Планировщик go оперирует 3-мя основными сущностями (важно понимать, что все это структуры, не пытайтесь переложить их на физическое восприятие):

• M — машина, поток операционной системы, которым она управляет;
• P — контекст планирования, необходимый для возможности переброски очередей планирования между потоками ( M );
• G — горутина, прежде всего там содержатся: стек, указатель команд, канал для планирования горутин.

При запуске программы на каждое виртуальное ядро процессора создается структура P , к которой привязывается отдельный поток M . Каждому P присваивается локальная очередь выполнения LRQ (есть еще глобальная очередь выполнения GRQ , этот вопрос я советую изучить самостоятельно). LRQ управляет горутинами в контексте P , переключением контекста M.

«В равной ли степени горутины делят между собой процессорное время?»

Существует 2 типа многозадачности:

• кооперативная — передачей управления процессы занимаются самостоятельно;
• вытесняющая многозадачность — планировщик дает отработать процессам равное время, после чего перещелкивает контекст.

С версии Go 1.14 планировщик с кооперативного стал асинхронно вытесняющим. Сделано это было по причине долго отрабатывающих горутин, надолго занимающих процессорное время и не дающих доступа до него другим горутинам. Теперь когда горутина отрабатывает больше 10 м/с Go будет пытаться переключить контекст для выполнения следующей горутины. Казалось бы вот он ответ. Но не все так просто. Части кооперативного поведения до сих пор присутствуют, к примеру перед вытеснением горутины необходимо выполнить проверку куска кода на атомарность, с точки зрения garbage collector . Операция вытеснения может настичь горутину в любом месте, в зависимости от состояния данных, сборщик мусора может отработать совсем не так как ожидалось. Так как Go живой язык, в который постоянно вносятся изменения, реализация и тонкости в разных версиях могут отличаться. Настоятельно советую обновлять свои знания по этой теме по мере релизов Go.

«Какие есть способы остановить все горутины в приложении?»

Если размышлять глобально, то таких способа 3:

• завершение main функции и main горутины;
• прослушивание всеми горутинами channel , при закрытии channel отправляется значение по умолчанию всем слушателям, при получении сигнала все горутины делают return ;
• завязать все горутины на переданный в них context .

«Как вручную задать количество процессоров P для приложения?»

Это позволяет сделать runtime.GOMAXPROCS() . Важно понимать, что при выставлении количества логических процессоров больше, чем есть у вас в системе, вы рискуете получить определенные проблемы с производительностью. Чтобы избежать этого можно задать runtime.GOMAXPROCS(runtime.NumCPU()) , runtime.NumCPU() — количество логических процессоров.

«Как принудительно переключить контекст?»

Переключение контекста вручную осуществляется с помощью функции runtime.Goshed().

«Как наладить связь между горутинами?»

Горутины общаются друг с другом посредством перегонки необходимых данных по channel . Именно о каналах идет речь знаменитом девизе Go: «Не общайтесь, делясь памятью; делитесь памятью, общаясь».

«Какие есть примитивы синхронизации?»

В используемые примитивы синхронизации можно записать:

• wait group ;
• mutex ;
• atomic ;
• sync map ;
• channel .

«Что такое wait group?»

sync.WaitGroup — это реализация счетчика, который можно инкрементировать и декрементировать, и самое главное остановить выполнение куска кода до того момента, пока значение счетчика не будет равно 0.

func main() < wg := sync.WaitGroup<>wg.Add(1) go gorutinePrint(&wg) wg.Wait() fmt.Println("hello from main") > func gorutinePrint(wg *sync.WaitGroup) < // без использования WaitGroup нет гарантий, что будет выведено fmt.Println("hello from goroutine") wg.Done() >

hello from goroutine hello from main

«Для чего используются mutex и какие бывают?»

Прежде чем ответить на этот вопрос, давайте немного поговорим о гонке данных. Гонка данных — это процесс, который возникает в Go приложении при условии:

• что 2 и более горутины используют одни и те же данные;
• 1 и более горутина используют данные на запись. В этом случае мы получаем ситуацию, когда наши данные могут стать неконсистентными. Во избежание этого необходимо определить правила, ограничивающие одновременную работу с данными. Для этих целей и были введены mutex . Их существует 2 вида:
• sync.Mutex — блокирует кусок кода как на запись, так и на чтение;
• sync.RWMutex — позволяет блокировать кусок кода только на запись.

// SafeCounter is safe to use concurrently. type SafeCounter struct < mu sync.Mutex v map[string]int >// Inc increments the counter for the given key. func (c *SafeCounter) Inc(key string) < c.mu.Lock() // Lock so only one goroutine at a time can access the map c.v. c.v[key]++ c.mu.Unlock() >// Value returns the current value of the counter for the given key. func (c *SafeCounter) Value(key string) int < c.mu.Lock() // Lock so only one goroutine at a time can access the map c.v. defer c.mu.Unlock() return c.v[key] >func main() < c := SafeCounterfor i := 0; i < 1000; i++ < go c.Inc("somekey") >time.Sleep(time.Second) fmt.Println(c.Value("somekey")) >

1000

«Для чего используется atomic?»

atomic — предоставляет набор атомарных функций, реализованных на аппаратном уровне. Это позволяет избегать гонки данных без блокировок. Вместе с этим, с помощью atomic в отличие от mutex можно делать только простые вещи, к примеру инкрементировать различные счетчики. Немного пояснений про атомарность: функция будет атомарной, если она завершается в один шаг по отношению ко всем другим потокам, которые имеют доступ к обрабатываемой памяти.

func main() < var ( counter uint64 wg sync.WaitGroup ) for i := 0; i < 10; i++ < wg.Add(1) go func() < for c := 0; c < 1000; c++ < atomic.AddUint64(&counter, 1) >wg.Done() >() > wg.Wait() fmt.Println("counter:", counter) >

counter: 10000

«Для чего используется sync map?»

Простой ответ на этот вопрос: достаточно частый кейс использования в Go mutex , который защищает данные в map . sync.Map можно рассматривать как map + RWMutex обертку. Но на деле этот ответ не совсем правильный, так как sync.Map решает одну довольно конкретную проблему cache contention . Что же это такое? При использовании sync.RWMutex в случае блокировки на чтение каждая горутина должна обновить поле readerCount , что происходит атомарно. Довольно обще процесс выглядит так:

• ядро процессора обновляет счетчик;
• ядро процессора сбрасывает кэш для этого адреса для всех других ядер;
• ядро процессора объявляет, что только оно знает действующее значение для обрабатываемого адреса;
• следующее ядро процессора вычитывает значение из кэша предыдущего;
• процесс повторяется. Так вот, когда несколько ядер хотят обновить readerCount , образуется очередь. И операция, которую мы считали константной, становится линейной относительно количества ядер. Именно решая эту проблему и ввели sync.Map . sync.Map рекомендуется применять именно на многопроцессорных системах.

// Lock locks rw for writing. // If the lock is already locked for reading or writing, // Lock blocks until the lock is available. func (rw *RWMutex) Lock() < if race.Enabled < _ = rw.w.state race.Disable() >// First, resolve competition with other writers. rw.w.Lock() // Announce to readers there is a pending writer. r := atomic.AddInt32(&rw.readerCount, -rwmutexMaxReaders) + rwmutexMaxReaders // Wait for active readers. if r != 0 && atomic.AddInt32(&rw.readerWait, r) != 0 < runtime_SemacquireMutex(&rw.writerSem, false, 0) >if race.Enabled < race.Enable() race.Acquire(unsafe.Pointer(&rw.readerSem)) race.Acquire(unsafe.Pointer(&rw.writerSem)) >>

«Что такое graceful shutdown?»

У каждого сервера есть потребность в его отключении, обычно это происходит при получении сигнала от ОС. И хорошо бы делать это отключение корректно, останавливая поэтапно все службы. Согласитесь никто из нас не выключает телевизор ударом табурета по корпусу. Так же и с сервером, для корректного отключения которого есть общие подходы. К примеру:

• создать канал, прослушивающий системные сигналы на выход;
• прослушивать этот канал;
• при получении сигнала поэтапно выходить из горутин;
• остановить сервер.

interrupter := make(chan os.Signal, 1) signal.Notify(interrupter, os.Interrupt) for range interrupter

Каналы в Golang

«Что такое channel?»

channel — это абстракция Go, которая помогает горутинам общаться друг с другом, передавая по channel значения. Канал можно представить как трубу, в которую одни горутины кладут данные, а другие их вычитывают. Под капотом channel представляет из себя 3 структуры ( hchan , sudog , waitq ). Наиболее интересной для нас является hchan , основные поля которой:

• qcount — количество элементов в буфере;
• dataqsiz — размерность буфера;
• buf — указатель на буфер для элементов канала;
• elemsize — размер элемента в канале;
• closed — флаг, указывающий, закрыт канал или нет (1/0 соответственно);
• elemtype — тип элемента;
• recvq — указатель на связанный список горутин, ожидающих чтения из канала;
• sendq — указатель на связанный список горутин, ожидающих запись в канал;
• lock — мьютекс для безопасного доступа к каналу. Когда мы создаем канал, мы присваеваем hchan elemtype и elemsize и аллоцируем структуру hchan в Heap .

type hchan struct < qcount uint // total data in the queue dataqsiz uint // size of the circular queue buf unsafe.Pointer // points to an array of dataqsiz elements elemsize uint16 closed uint32 elemtype *_type // element type sendx uint // send index recvx uint // receive index recvq waitq // list of recv waiters sendq waitq // list of send waiters // lock protects all fields in hchan, as well as several // fields in sudogs blocked on this channel. // // Do not change another G's status while holding this lock // (in particular, do not ready a G), as this can deadlock // with stack shrinking. lock mutex >

«Что такое буферизированный и небуферизированный channel?»

channel делятся на два типа по наличию/отсутствию буфера. Соответственно в первом случае поле dataqsiz будет равно размеру переданного буфера (3), а поле buf будет ссылкой на этот буфер. Во втором случае поле dataqsiz будет равно 0, а поле buf будет nil. Отсюда возникает различное поведение этих типов channel при операциях с ними. Об этом мы поговорим ниже.

chanBuf := make(chan bool, 3) chanIsNotBuf := make(chan bool)

«Какие действия можно произвести с каналом?»

С channel можно сделать 4 действия:

• создать канал;
• записать что-то в канал;
• что-то вычитать из канала;
• закрыть канал.

myChan := make(chan int) myChan 

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool < if c == nil < if !block < return false >gopark(nil, nil, waitReasonChanSendNilChan, traceEvGoStop, 2) throw("unreachable") > . >

func chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) < // raceenabled: don't need to check ep, as it is always on the stack // or is new memory allocated by reflect. if debugChan < print("chanrecv: chan=", c, "\n") >if c == nil < if !block < return >gopark(nil, nil, waitReasonChanReceiveNilChan, traceEvGoStop, 2) throw("unreachable") > . >

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool < . if c.closed != 0 < unlock(&c.lock) panic(plainError("send on closed channel")) >. >

func printNum(c chan int) < for i := 0; i > func main() < // без блокировок fmt.Println("start") defer fmt.Println("stop") c := make(chan int, 3) go printNum(c) c

start stop

func printNum(c chan int) < for i := 0; i > func main() < // с блокировкой fmt.Println("start") defer fmt.Println("stop") c := make(chan int, 3) go printNum(c) c 
start 1 2 3 4 stop
"Что будет если писать/читать в/из небуферизированный channel?"
Небуферизированный канал - это тот же буферизированный канал, но с nil буфером. Соответственно принцип его работы будет таким же. Чтение из пустого и запись в непустой небуферизированный канал являются блокирующими операциями.
"Как закрыть channel? Что с ним происходит?"
Для закрытия канала предусмотрена функция close . Если упрощенно (опускаем блокировки), то при закрытии канала происходят следующие действия:

проверка, что канал инициализирован и не является nil ( panic - если это не так);
проверка, что канал не закрыт ( panic - если это не так);
поле closed hchan выставляется в 1 (true);
отправка всем ожидающим чтения default value типа данных в канале;
ожидающие записи получают panic . Интересный момент, что так как закрытие канала не блокирует чтение канала, то данные из буфера канала можно вычитать и после его закрытия.

func closechan(c *hchan) < if c == nil < panic(plainError("close of nil channel")) >lock(&c.lock) if c.closed != 0 < unlock(&c.lock) panic(plainError("close of closed channel")) >. c.closed = 1 var glist gList // release all readers for < sg := c.recvq.dequeue() if sg == nil < break >if sg.elem != nil < typedmemclr(c.elemtype, sg.elem) sg.elem = nil >. gp := sg.g gp.param = unsafe.Pointer(sg) sg.success = false if raceenabled < raceacquireg(gp, c.raceaddr()) >glist.push(gp) > // release all writers (they will panic) for < sg := c.sendq.dequeue() if sg == nil < break >sg.elem = nil if sg.releasetime != 0 < sg.releasetime = cputicks() >gp := sg.g gp.param = unsafe.Pointer(sg) sg.success = false if raceenabled < raceacquireg(gp, c.raceaddr()) >glist.push(gp) > . >
"Какие есть инструкции для чтения из channel?"
Из канала можно читать значения:

присваивая их в переменную;
прослушивая канал с помощью инструкции for range ;
прослушивая канал с помощью инструкции select case . Также следует обратить внимание, что чтение из закрытого канала отдает дефолтное значение типа данных канала. Поэтому существует возможность проверить, что при чтении получено значение из буфера. Для этого используется синтаксис со второй ( bool ) переменной val, ok :=

func main()
func main() < queue := make(chan string, 2) queue >
one two
func main() < ch1 := make(chan string) ch2 := make(chan string) go func() < ch1 () go func() < ch2 () for i := 0; i < 2; i++ < select < case msg1 := > >
chan2: two chan1: one
"Как сделать select неблокирующим?"
Инструкция select в предыдущем примере является блокирующей, так как на каждый виток цикла будет происходить ожидание одного из case . Но есть возможность задать поведение для select по умолчанию, то есть для случаев, когда не выполняются case . Для этого необходимо добавить инструкцию default . Таким образом, когда не срабатывает ни один из case будет срабатывать кусок кода под инструкцией default.
"Какой порядок исполнения операций case в select?"
Первым выполнится тот case в select , который будет готов. При одновременной отправке данных в каналы, прослушиваемые в select порядок операций не гарантирован.
Контексты в Golang
"Что такое context?"
По сути context - это некий сборник метаданных, который можно привязать к какому-нибудь процессу. К примеру для HTTP вызова можно объявить context , записать туда куки и иную информацию о пользователе. По окончанию вызова context можно отменить.
"Для чего применяется context?"
У context два основных применения:

для отмены выполнения либо по таймауту, либо по дедлайну. Тот же пример с HTTP запросами;
для передачи параметров. Правда злоупотребление этим плохо сказывается на явности кодовой базы. Обязательные параметры передавать через context все же не стоит.

"Чем отличается context.Background от context.TODO?"
И context.Background() и context.TODO() это одно и то же. Разница лишь в том, что context.TODO() выставляется в местах, где пока нет понимания, что необходимо использовать context.Background() и возможно его надо заменить на дочерний контекст.
"Как передавать значения и вычитывать их из context?"
В пакете context существует функция context.WithValue(parent Context, key, val interface<>) Context , которая от родительского контекста создает производный и добавляет в него по key значение. Извлекая значение из context необходимо помнить, что на выход получаем интерфейс, который необходимо правильно скастить.
func main() < type favContextKey string f := func(ctx context.Context, k favContextKey) < if v := ctx.Value(k); v != nil < fmt.Println("found value:", v) return >fmt.Println("key not found:", k) > k := favContextKey("language") ctx := context.WithValue(context.Background(), k, "Go") f(ctx, k) f(ctx, favContextKey("color")) >
found value: Go key not found: color
"Каковы отличия context.WithCancel, context.WithDeadline, context.WithTimeout?"

context.WithCancel(parent Context) (ctx Context, cancel CancelFunc) создает контекст производный от родительского, также возвращает функцию отмены, с помощью которой этот контекст можно закрыть. Общепринятой практикой является работать с функцией отмены там, где она получена, не передавая ее глубже.
context.WithDeadline(parent Context, d time.Time) (ctx Context, cancel CancelFunc) создает контекст производный от родительского, также возвращает функцию отмены, с помощью которой этот контекст можно закрыть. Контекст автоматически отменится в переданное, как входной параметр функции, время.
context.WithTimeout(parent Context, timeout time.Duration) (ctx Context, cancel CancelFunc) создает контекст производный от родительского, также возвращает функцию отмены, с помощью которой этот контекст можно закрыть. Контекст автоматически отменится через интервал времени, переданный, как входной параметр функции.

"Как обрабатывать отмену context?"
func main() < ctx, cancelFunc := context.WithCancel(context.Background()) numChan := make(chan int) go work(ctx, numChan) go func() < for i := 0; i < 5; i++ < numChan >() cancelFunc() time.Sleep(1 * time.Second) > func work(ctx context.Context, numChan chan int) < for < select < case > >
Вывод (может отличаться по количеству num)
0 stop
Память в Golang
"Как реализовано хранилище памяти в Go?"
Хранилища памяти в Go реализованы с помощью двух подходов:

хранение в stack ;
хранение в heap . stack в основном используется для хранения локальных переменных, аргументов функции. Из плюсов - stack достаточно легко очищается. Из минусов - при аллокациях на stack существуют копии одних и тех же значений, которые надо хранить и обрабатывать. heap в основном используется для хранения глобальный переменных и ссылочных типов. Из плюсов - при аллокациях на heap существует всегда одно уникальное значение, которое надо хранить и обрабатывать. Из минусов - heap тяжело очищается, так как приходится запускать сборщик мусора, который имеет много накладных расходов и останавливает приложение.

"Что обозначает * и &?"
& - это адрес блока памяти. То есть &myVar - это адрес того места в памяти, где хранятся данные переменной myVar . Тогда как * можно использовать в двух вариантах:

чтобы объявить тип-указатель var pointVar *int . В данном случае указатель на int ;
чтобы получить значение по адресу *pointVar . Обратный предыдущему процесс, и здесь мы получим значение по адресу pointVar .

func main()
something 0xc000096230 0xc000096230 something
"Как происходит передача параметров в функцию?"
Параметры в Go всегда передаются по значению. Это значит, что всякий раз, когда мы передаем аргумент в функцию, функция получает копию первоначального значения. Чтобы работать именно с той же самой переменной, не копируя ее, необходимо использовать адрес этой переменной. При этом сам указатель будет скопирован.
func main() < str := "someString" fmt.Println("first val:", str) dontCahngeStr(str) fmt.Println("after dontCahngeStr val:", str) fmt.Println("val addr in main:", &str) cahngeStr(&str) fmt.Println("after cahngeStr val:", str) fmt.Println("val addr in main:", &str) >func dontCahngeStr(str string) < str = "nextStr" >func cahngeStr(str *string)
first val: someString after dontCahngeStr val: someString val addr in main: 0xc000010070 addr addr in cahngeStr: 0xc00000e030 after cahngeStr val: nextStr val addr in main: 0xc000010070
"Есть ли особенности поведения при передаче map и slice в функцию?"
Передача slice и map может заставить усомниться в том, что они передаются в функцию по значению. Однако здесь так же происходит копирование. Структуры slice и map копируются, однако в самих структурах содержатся ссылки на области памяти, благодаря которым создается эффект передачи по ссылке.
func main() < slice := []intfmt.Println(slice) fmt.Printf("%p\n", &slice) changeZeroElem(slice) fmt.Println(slice) > func changeZeroElem(slice []int)
[1 2 3 4 5] 0xc0000ac018 0xc0000ac048 [99 2 3 4 5]
func main() < store := map[string]intfmt.Println(store) fmt.Printf("%p\n", &store) changeMapElem(store) fmt.Println(store) > func changeMapElem(store map[string]int)
map[first:1 second:2] 0xc0000b2018 0xc0000b2028 map[first:99 second:2]
"Как функции делятся памятью?"
В начале следует сказать про фрейм. Фрейм можно представить как отдельное пространство памяти для конкретной функции. Функция может работать с памятью в своем фрейме, однако не может работать с памятью фреймов других функций. Когда из одной функции мы вызываем другую функцию, происходит переход фреймов. Чтобы использовать какие-то данные предыдущего фрейма в следующем их можно передать по значению. Если необходимо работать не с копией, а именно переменной другого фрейма, необходимо использовать переменные-указатели, которые обеспечивают доступ до переменных других фреймов.
"Можно ли явно аллоцировать переменную в стэке или куче?"
Способа явно сказать компилятору Go, где аллоцировать переменную, в куче или в стеке не существует. Но это можно сделать косвенно - стилем написания кода. Решающую роль здесь играет, то, как значение будет использоваться в программе.
Сборщик мусора в Golang
"Что такое сборщик мусора и по какому алгоритму он реализован в Go?"
Любую аллоцированную память необходимо очищать после окончания ее использования. В некоторых языках программирования разработчик сам должен управлять этим процессом. В Go неиспользуемые объекты находит и удаляет сборщик мусора. Сборщик мусора - устроен по алгоритму Mark and Sweep (реализация может поменяться, необходимо просматривать изменения).
"Расскажите про алгоритм mark and sweep"
Алгоритм Mark and Sweep состоит из двух частей:


Mark разметка;
Sweep очистка памяти. Сама стадия Mark реализована с помощью 3 цветного алгоритма. Для наглядности представим, что все наши данные лежат в виде графа, все узлы графа помечаем белым цветом. Алгоритм:


идет сканирование объектов первого уровня доступа, тех которые хранятся либо глобально, либо в стэке потока;
объекты первого уровня помечаются серым цветом;
в каждом сером объекте ищутся ссылки на области памяти;
объекты по ссылкам помечаются серым;
сам родительский элемент помечается черным;
процесс повторяется, пока не останется серых объектов (белые объекты будем удалять на следующем шаге).

Прежде чем переходить к самому алгоритму необходимо разобрать два понятия stop the world и write barrier.
write barrier - в рамках этой статьи мы будем рассматривать его как некий черный ящик. Основная его цель - контролировать, чтобы сборщик мусора правильно выстраивал и обрабатывал "граф" данных, так как объекты могут перемещаться и иже.
Упрощенный алгоритм сборщика мусора (на момент работы программы, то есть сборщик мусора уже отработал один или больше циклов):

завершение цикла очистки Sweep , на этом этапе вызывается stop the world , ожидается пока все горутины достигнут точки безопасности, завершается очистка ресурсов;
начало цикла Mark , на этом этапе включается write barrier , start the world , сканируются глобальные переменные, выполняется трехцветный алгоритм;
завершение цикла Mark , на этом этапе вызывается stop the world , после выполнения задач очищаются кэши, завершается разметка;
начало цикла очистки Sweep , на этом этапе выключается write barrier , start the world , дальнейшая очистка ресурсов происходит в фоне.

"Когда запускается сборщик мусора?"
По умолчанию сборщик мусора запускается в тот момент, когда heap увеличился вдвое. Этот параметр также можно настроить с помощью переменной среды окружения GOGC . Вручную сборщик мусора можно запустить с помощью runtime.GC().
"Каковы ресурсы, которые потребляет сборщик мусора?"
Сборщик мусора потребляет до 25% CPU для фазы Mark . Помимо этого за цикл работы сборщика мусора два раза происходит остановка приложения (вызов stop the world ).
Заключение
Далеко не все аспекты, которые можно спросить на собеседовании удалось осветить в формате статьи. Также Go развивающийся язык и определенная информация может устаревать от версии к версии. По этим причинам, при подготовке в интервью, призываю вас не останавливаться только на изложенных здесь вопросах и ответах, изучайте свой инструмент, это окупится!
Буду признателен любым конструктивным замечаниям. Спасибо!
Спасибо за конструктивные замечания к статье как до, так и после ее выкладки: @user862 , @JimTheBeam .
К сожалению, не доступен сервер mySQL


Похожие публикации:

Font weight css что это
Континент ап какой порт
Сериалайзер что это
Что происходит в runtime golang