a very not-merged-pull-request implementation for lru_cache utility from fuctools in Chapel

LRU_caching.chpl

private use Map only;
private use List only;
private use Crypto only;

record ordered_map {
    /* Type of map keys.*/
    type keyType;
    /* Type of map values*/
    type valType;

    var dictionary : Map.map(keyType, valType, parSafe = true);
    var keysOrder : List.list(keyType);

    proc init(type keyType, type valType) {        
        this.keyType = keyType;
        this.valType = valType;
    }

    proc insert(k: keyType, v: valType) {
        var success = dictionary.add(k, v);         
        if success {
            keysOrder.append(k);
        } else {              
            keysOrder.remove(k);                    // we want this key on the front if we insert it again
            keysOrder.insert(1, k);                 // to have the "LRU" value on the front and least used value at the back
        }                                           // "L" in "LRU" stands for last not least for now
        return success;
    }

    proc available(k: keyType) : bool {
        return dictionary.contains(k);
    }

    proc remove(k: keyType) : bool {
        var success = dictionary.remove(k);
        if success {
            var h = keysOrder.remove(k);
        }
        return success;
    }

    proc removeLast() : bool {                     // when our cache is full
        var lastElement = keysOrder.pop();
        var success = dictionary.remove(lastElement);
        return success;
    }

    proc this(k: keyType) {
        return dictionary[k];
    }

    proc printValues() {
        for i in this.keysOrder {
            writeln(i);
        }
    }
}


class lru_cache {
    var function;                                   // the function whose values are cached
    var size: int;
    var counter : int;
    type outputs;
    var dictionary : ordered_map(string, outputs);
    var hashingObject = new Crypto.Hash(Crypto.Digest.SHA256);      // hashing utility

    proc init(f, s, exampleOut) {   // f is the function, s is the size of the cache, counter is supposed to track how many items in our cache
        function = f;
        size = s;
        counter = 0;
        outputs = exampleOut.type;  // to ge the type of the output
    }

    proc call(i) where isTuple(i) == true {

        var cryptoBuffer = new Crypto.CryptoBuffer(i:string);     
        var hashed = ((hashingObject.getDigest(cryptoBuffer)).buff):string;

        if dictionary.available(hashed) {
            dictionary.insert(hashed, dictionary[hashed]);       // to make it at the front of list
            return dictionary[hashed];
        } else {
            var newResult = function((...i));
            dictionary.insert(hashed, newResult);
            counter = counter + 1;
            return newResult;
        }
    }
}




// the variable b is here to demonstrate that lru_cache class can handle functions with multiple arguments


proc fibonacci(n: int, b: int) : int {
    if n <= 1 {
        return 1;
    } else {
        return fibonacci(n-1, b) + fibonacci(n-2, b);
    }
}

var a = fibonacci(43,10);           // the second variable "10" is just a dummy variable

var cachingObject = new lru_cache(fibonacci, 100, 5);       // the constructor takes the function, and the size of the cache "dummy variable for now", and output of the function to get its type

// let's see the difference in times 
use Time;

var startTime1 = getCurrentTime();
var output1 = cachingObject.call((30,10));  // the input MUST be passed as tuple, because we need to have a way to refer to the input as a whole
writeln(getCurrentTime() - startTime1);     // and we don't have *args or *kwargs like in python

var startTime2 = getCurrentTime();
var output2 = cachingObject.call((30,10));
writeln(getCurrentTime() - startTime2);