Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Entendendo Alocação de Memória no Go

Entendendo Alocação de Memória no Go

Em Go, graças ao garbage collector, não precisarmos nos preocupar em gerenciar manualmente a memória alocada. Tanto o compilador como o runtime da linguagem desempenham papéis fundamentais no processo de alocação de memória. Que tal entender como eles fazem isso?

Nessa palestra, iremos mergulhar no funcionamento dos alocadores de memória, e entenderemos como estes interagem com o Sistema Operacional e gerenciam a memória alocada.

Aprenderemos como funciona o algoritmo utilizado pelo runtime do Go para alocação de memória, qual o papel do compilador e porque conhecer os internos da linguagem pode ajudar a escrever códigos mais otimizados (e quando não fazer isso).

André Carvalho

July 21, 2018
Tweet

More Decks by André Carvalho

Other Decks in Programming

Transcript

  1. 3

  2. Por que? • Conhecer os trade-offs • Conhecer uma camada

    de abstração abaixo • Porque não? 4
  3. 6 $ ./vmemory 53 at 0xc420016110 $ ./vmemory 68 at

    0xc420016110 Rodando o programa duas vezes ao mesmo tempo... Mesmo endereço
  4. Memória Virtual • Processos não leem diretamente da memória física

    ◦ Segurança ◦ Coordenação entre múltiplos processos • Memória Virtual abstrai isso dos processos ◦ Segmentation ◦ Page tables 7
  5. Memória Virtual 8 Frame 0 Frame 1 Frame 2 Frame

    3 Frame 4 Frame 5 Frame 6 Frame 7 RAM Disk Other process Page 0 Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7 Page Process Frame Page Table 3 6
  6. Layout de um Processo 9 Text Data Heap BSS Stack

    Program Break Code Initialized static variables Uninitialized static variables Dynamic allocated variables Function stack frames
  7. Alocação na Stack 10 Stack Used Stack Pointer (SP) Unused

    Allocation SP += size; return Stack[SP-size]; Deallocation SP -= size;
  8. Alocação na Heap • Objetos com tamanho conhecido apenas em

    tempo de execução • C tem malloc e free • C++ tem new e delete • Go usa escape analysis e garbage collection 11
  9. Alocador Simples 14 Application Allocator OS malloc mmap Alocador utiliza

    syscalls como mmap/munmap para falar com o OS munmap madvise free
  10. Alocador Simples 17 Virtual Address Space 0x000000c000000000 mmap( 0x000000c000000000, 4096,

    PROT_WRITE | PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, ...) Start Address Size Permission Flags
  11. Alocador Simples - Alocação malloc(10) 20 4062 Head 10 P

    Allocator returns p, which points right after the header
  12. Alocador Simples • Pode ser implementado em algumas centenas de

    LOCs • Questões não endereçadas ◦ Fragmentação ◦ Devolver memória para o OS ▪ Quando? ▪ Como? munmap, madvise... ◦ Multi-thread ◦ ... 23
  13. Thread-Caching Malloc (TCMalloc) • Implementado originalmente em C pelo Google

    • Serve como base para o algoritmo usado pelo Go • Diminui lock-contention em programas multi-threaded 25
  14. TCMalloc • Cada thread tem um cache local • Dois

    tipos de alocação ◦ Small allocations (<= 32 kB) ◦ Large allocations 26
  15. TCMalloc - Small Allocations • Atendidas pelo cache local da

    thread • Tamanho é arredondado para o de uma das classes 27 malloc(965 bytes) ⇒ malloc(1024 bytes) malloc(1023 bytes) ⇒ malloc(1024 bytes)
  16. TCMalloc - Small Allocations Class 0 Class 1 Class 2

    ... Local Thread Cache Span Span Span ... Central Free List Class 1 30 Run of contiguous pages Span
  17. TCMalloc - Small Allocations Class 0 Class 1 Class 2

    ... Local Thread Cache Span Span Span ... Central Free List Class 1 31
  18. TCMalloc - Small Allocations Span Span Span Central Free List

    Class X Span 1 page 2 pages ... > 255 pages Span Span Span Span Span Span Span Central Heap 32
  19. TCMalloc - Small Allocations Span Span Span Central Free List

    Class X Span 1 page 2 pages ... > 255 pages Span Span Span Span Span Span Central Heap Span ... 33 Span
  20. TCMalloc - Small Allocations Application Local Thread Cache Central Free

    List Central Heap 4 bytes N 8-byte objects X pages OS Y*X pages 34 X pages N 8-byte objects Y*X pages
  21. TCMalloc - Large Allocations • Atendidas pela Heap central •

    Tamanho é arredondado para numero de paginas 35 malloc(34 kB) ⇒ malloc(36 kB) ⇒ 9 pages malloc(33 kB) ⇒ malloc(36 kB) ⇒ 9 pages
  22. TCMalloc - Large Allocations 1 page 2 pages ... >

    255 pages Span Span Span Span Span Span Central Heap Span Span 36
  23. TCMalloc - Deallocation Page 1 Page 2 Page 3 Page

    4 Page 5 Page 6 Span A Span B Span C 37
  24. TCMalloc - Deallocation free( ) Page Span Class 0 Class

    1 Class 2 ... Local Thread Cache Small object 39
  25. TCMalloc - Deallocation free( ) Page Span Large object Page

    1 Page 2 Page 3 Page 4 Span A Span B Span C 40
  26. TCMalloc - Deallocation free( ) Page Span Large object Page

    1 Page 2 Page 3 Page 4 Span A Span B 41
  27. TCMalloc - Deallocation free( ) Page Span Large object 1

    page 2 pages ... > 255 pages Span B Central Heap 42
  28. TCMalloc - Deallocation free( ) Page Span Large object 1

    page 2 pages ... > 255 pages Span B Central Heap 43
  29. package main func main() { f() } //go:noinline func f()

    *int { i := 10 return &i } 46 $ go build -gcflags "-m -m" main.go # command-line-arguments ./main.go:8:6: cannot inline f: marked go:noinline ./main.go:3:6: cannot inline main: non-leaf function ./main.go:10:9: &i escapes to heap ./main.go:10:9: from ~r0 (return) at ./main.go:10:2 ./main.go:9:2: moved to heap: i
  30. 47 $ go tool compile -S main.go ... 0x001d 00029

    (main.go:9) LEAQ type.int(SB), AX 0x0024 00036 (main.go:9) MOVQ AX, (SP) 0x0028 00040 (main.go:9) PCDATA $0, $0 0x0028 00040 (main.go:9) CALL runtime.newobject(SB) ...
  31. 48 $ go tool compile -S main.go ... 0x001d 00029

    (main.go:9) LEAQ type.int(SB), AX 0x0024 00036 (main.go:9) MOVQ AX, (SP) 0x0028 00040 (main.go:9) PCDATA $0, $0 0x0028 00040 (main.go:9) CALL runtime.newobject(SB) ... func newobject(typ *_type) unsafe.Pointer { return mallocgc(typ.size, typ, true) }
  32. Go’s Allocator • Acoplado ao GC e outras partes do

    runtime ◦ Difícil de trocar por outras implementações • Três tipos de alocação ◦ Tiny Allocations (no pointers, size < 16 bytes) ◦ Small Allocations (size <= 32 kbytes) ◦ Large Allocations 50
  33. Go’s Allocator - Large Allocations 51 1 page 2 pages

    ... > 255 pages Span Span Span Span Span Span mheap Busy Spans Span Span Span Antes de alocar, mheap faz o sweep do mesmo número de paginas
  34. Go’s Allocator - Large Allocations 52 1 page 2 pages

    ... > 255 pages Span Span Span Span Span Span Span Span Span Span Span mheap Free Spans
  35. Go’s Allocator - Large Allocations 53 1 page 2 pages

    ... > 255 pages Span Span Span Span Span Span mheap Free Spans Span Span Span Span Span mtreap ⇒ randomized binary tree
  36. Go’s Allocator - Large Allocations 54 Depois de alocar, dependendo

    da quantidade de memória em uso... • A goroutine pode ter que trabalhar para o GC • Stop the World
  37. Go’s Allocator - Small Allocations 55 P 1 mcache Cada

    processador lógico (P) tem um cache local (mcache) P 2 mcache
  38. Go’s Allocator - Small Allocations 56 P 1 P 2

    mcache mcache Cada mcache mantem um span para cada tamanho (size class) Span Span ... class 1 class 2 Span Span ... class 1 class 2
  39. Go’s Allocator - Small Allocations 57 class bytes/obj bytes/span objects

    1 8 8192 1024 2 16 8192 512 3 32 8192 256 4 64 8192 170 ... 65 28672 57344 2 66 32768 32768 1
  40. Go’s Allocator - Small Allocations 58 P 1 mcache mcache

    retorna o endereço de um objeto livre no span Span Span ... class 1 class 2 Span
  41. Go’s Allocator - Small Allocations 59 P 1 mcache mcache

    pede um novo span para o mcentral dessa size class Span Span ... class 1 class 2 Span
  42. Go’s Allocator - Small Allocations 60 P 1 mcache Cada

    mcentral tem duas listas, empty e nonempty spans Span Span ... ... class 1 class 2 mcentral mcentral Span Span Span Span
  43. Go’s Allocator - Small Allocations 61 P 1 mcache Span

    com objetos livres vai ser entregue ao mcache Span ... ... class 1 class 2 mcentral mcentral Span Span Span Span
  44. Go’s Allocator - Small Allocations 62 P 1 mcache mcentral

    vai tentar fazer sweep de spans vazios Span Span ... ... class 1 class 2 mcentral mcentral Span Span If there are no nonempty spans….
  45. Go’s Allocator - Small Allocations 63 Se nada funciona, mcentral

    vai pedir um novo span para a mheap class 0 mcentral Span Span mheap
  46. Go’s Allocator - Small Allocations 64 mcentral vai dar esse

    span para a mcache class 0 mcentral Span Span mheap Span
  47. Go’s Allocator - Tiny Allocations Alocações para objetos sem pointers

    menores que < 16 bytes The main targets of tiny allocator are small strings and standalone escaping variables. On a json benchmark the allocator reduces number of allocations by ~12% and reduces heap size by ~20%. 65
  48. 66 Go’s Allocator - Tiny Allocations 64 bytes Allocated Free

    Allocated Free • Cada P mantem um objeto de 64-bytes que foi alocado de um span • Cada tiny allocation adiciona um subobjeto ao final do objeto • O GC não sabe sobre esses subobjetos!
  49. 67 Go’s Allocator - Tiny Allocations Allocated Free mcache P

    1 • Pega um novo bloco do mcache ≃ small allocation • Eventualmente, o GC vai coletar o bloco antigo Free P 1 mcache
  50. Garbage Collector ⇒ Concurrent mark and sweep 68 Go’s Allocator

    - Sweeping 1. Scan all objects 2. Mark objects that are live 3. Sweep objects that are not live
  51. • Runtime periodicamente devolve memória ao OS • Devolve spans

    que foram garbage collected a mais de 5 minutos • No Linux, usa a syscall madvise(2) 69 Go’s Allocator - Devolvendo memória ao OS madvise(addr, size, _MADV_DONTNEED)
  52. 71 stats := runtime.MemStats{} runtime.ReadMemStats(&stats) type MemStats struct { ...

    // Heap memory statistics. HeapAlloc uint64 HeapSys uint64 HeapIdle uint64 HeapInuse uint64 HeapReleased uint64 HeapObjects uint64 ... }
  53. Referências 1. http://goog-perftools.sourceforge.net/doc/tcmalloc.html 2. https://www.ardanlabs.com/blog/2017/05/language-mechanics-on-stacks-and-pointers.html 3. https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/ 4. Lec 10

    | MIT 6.172 Performance Engineering of Software Systems, Fall 2010 5. https://faculty.washington.edu/aragon/pubs/rst89.pdf 6. http://man7.org/linux/man-pages/man2/mmap.2.html 7. http://man7.org/linux/man-pages/man2/madvise.2.html 8. https://github.com/andrestc/linux-prog/blob/master/ch7/malloc.c 72