moonbitlang / core

MoonBit's Core library
https://moonbitlang.com/
Apache License 2.0
483 stars 54 forks source link

better layout for hashmap #466

Closed bobzhang closed 1 month ago

bobzhang commented 1 month ago

change the current layout into

priv enum Entry[K, V] {
  Empty
  Valid(
    mut ~psl : Int,
    ~hash : Int,
    ~key : K,
    mut ~value : V,
    mut ~prev : Entry[K, V],
    mut ~next : Entry[K, V]
  )
} 

struct LinkedHashMap[K, V] {
  mut entries : FixedArray[Entry[K, V]]
  mut size : Int // active key-value pairs count
  mut capacity : Int // current capacity 
  mut growAt : Int // threshold that triggers grow
  mut head : Entry[K, V] // head of linked list
  mut tail : Entry[K, V] // tail of linked list
}
struct Entry[K,V] {
  mut psl : Int
  hash : Int 
  key : K
  mut value : V
  mut prev : Option[Entry[K,V]]
  mut next : Option[Entry[K,V]]
}

struct LinkedHashMap [K,V] {
  mut entries : FixedArray[Option[Entry[K, V]]]
  mut size : Int // active key-value pairs count
  mut capacity : Int // current capacity 
  mut growAt : Int // threshold that triggers grow
  mut head : Option[Entry[K, V]] // head of linked list
  mut tail : Option[Entry[K, V]] // tail of linked list
}

The rationale is that now Option is unboxed, None is a nullptr, FixedArray::make(size, None) could be specialized into a single instruction, HashMap array initialization will be faster

cc @yj-qin