lock_free/Sieve_Cache.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion feature lock_free.Sieve_Cache
#
# -----------------------------------------------------------------------


private:public Node(K type, V type, pair (K,V), visited concur.atomic bool, prev concur.atomic (option (lock_free.Node K V)), next concur.atomic (option (lock_free.Node K V))) ref is
  public redef as_string String => "($(pair.0),$(pair.1))"


# "SIEVE is a cache eviction algorithm that decides what to keep in the cache and what to discard.
#  It achieves both simplicity and efficiency."
# source: https://sievecache.com/
# paper : https://junchengyang.com/publication/nsdi24-SIEVE.pdf
#
# example usage:
#     cache0 := lock_free.Sieve_Cache String i32 3
#     say <| cache0.access "A" ()->1    # => 1
#     say <| cache0.access "B" ()->2    # => 2
#     say <| cache0.access "C" ()->3    # => 3
#     say <| cache0.access "A" ()->4    # => 1
#     say <| cache0.access "D" ()->5    # => 5
#     say <| cache0.access "C" ()->6    # => 3
#
public Sieve_Cache(K type : property.hashable, V type, MM type : container.Mutable_Map K (lock_free.Node K V), public capacity i64) ref is

  cache := MM .empty

  # Using atomic here to be able to read and write in a
  # multi threaded environment.
  head  := concur.atomic (option (lock_free.Node K V)) .new nil
  tail  := concur.atomic (option (lock_free.Node K V)) .new nil
  hand  := concur.atomic (option (lock_free.Node K V)) .new nil


  # add Node n to head
  #
  add_to_head(n lock_free.Node K V) =>
    n.next.write head.read
    n.prev.write nil
    match head.read
      h lock_free.Node => h.prev.write n
      * =>
    head.write n
    match tail.read
      nil => tail.write n
      * =>


  # remove Node n
  #
  remove_node(n lock_free.Node K V) =>
    match n.prev.read
      prev lock_free.Node => prev.next.write n.next
      nil => head.write n.next

    match n.next.read
      nxt lock_free.Node => nxt.prev.write n.prev
      nil => tail.write n.prev

    n.prev.write nil
    n.next.write nil


  # evict first unvisited node
  #
  evict =>
    init_obj => match hand.read
                  h lock_free.Node => h
                  nil => tail.read
    for obj := init_obj, match obj.or_panic.prev.read
                           p lock_free.Node => p
                           nil => tail.read
    while obj >>? (.visited.read) do
      obj.or_panic.visited.write false
    else
      match obj
        o lock_free.Node =>
          hand.write o.prev
          _ := cache.remove o.pair.0
          remove_node o
        nil => hand.write nil


  # get stored value for key k
  #
  public get(key K) option V =>
    match cache[key]
      # cache miss
      nil =>
        nil
      # cache hit
      n lock_free.Node =>
        n.visited.write true
        n.pair.1


  # access stored value for key,
  # if not in cache, compute and store in cache
  #
  public access(key K, val ()->V) V =>
    match cache[key]
      # cache miss
      nil =>
        v := val()
        if cache.size >= capacity
          evict
        new_node := lock_free.Node (key, v) (concur.atomic bool .new false) (concur.atomic (option (lock_free.Node K V)) .new nil) (concur.atomic (option (lock_free.Node K V)) .new nil)
        add_to_head new_node
        cache.put key new_node
        new_node.visited.write false
        v
      # cache hit
      n lock_free.Node =>
        n.visited.write true
        n.pair.1


  public redef as_string String =>
    for res := "", res + "$(n.or_panic) (Visited: $(n.or_panic.visited.read))" + (if n.or_panic.next.read.ok then " -> " else "")
        n := head.read, n.or_panic.next
    while n.ok
    else
      res