No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Sistema de caché con concurrencia

6/19
Recursos

Aportes 8

Preguntas 1

Ordenar por:

Los aportes, preguntas y respuestas son vitales para aprender en comunidad. Regístrate o inicia sesión para participar.

Se ha empeorado notablemente el rendimiento en esta clase.
Realmente no se hace uso del sistema de cache en la ejecución de los ejemplos. Ahora ya ninguno se calcula en nanosegundos.
Se han metido elementos de control de bloqueo en un problema que no lo requiere. No es un buen ejemplo docente.
Tampoco se ha diseñado para poder usar el potencial de la cache en la función de fibonacci. No tiene sentido que si ya se ha calculado el valor fib(42), para calcular el fib(41) le cueste prácticamente lo mismo porque no ha cacheado los resultados intermedios.
No se puede vender esto como un éxito con un resultado manifiestamente peor que el anterior y que encima realmente no usa la cache en ningún momento para beneficiarse de ella, teniendo resultados iguales o peores (el 41 tarde incluso el doble).
Un desastre de clase.

Hice algunos cambios en el main para denotar más el uso de cache al buscar el número 42. La primera vez toma 12s, pero el resto de las veces tarda unos pocos ns.

Básicamente lo que hice fue agregar un canal

channel := make(chan int, maxGoroutines) 

para limitar la cantidad de goroutines que calculan. Use solo dos goroutines para evitar que varias Goroutines entren a calcular de forma simultánea el mismo número.

func main() {
	cache := NewCache(GetFibonacci)
	fibo := []int{42, 41, 38, 40, 38, 42, 42, 42, 42, 42, 42}

	var wg sync.WaitGroup

	maxGoroutines := 2
	channel := make(chan int, maxGoroutines)

	for _, value := range fibo {
		wg.Add(1)

		go func(valueFibo int) {
			defer wg.Done()

			channel <- 1

			start := time.Now()
			result, err := cache.Get(valueFibo)
			if err != nil {
				log.Println(err)
			}

			fmt.Printf("Calculate: %d, Time: %s, Result: %d\n", valueFibo, time.Since(start), result)

			<-channel
		}(value)

	}
	wg.Wait()
}

En esta clase no se logró el objetivo de utilizar concurrencia porque a la final se demora igual o más para calcular el fibonacci de los números repetidos.

Quedé decepcionado, profesor sinceramente le faltó más profundización en este ejemplo

Mi codigo con comentarios y con los channles que comento el usuario Tan:

package main

import (
	"fmt"
	"sync"
	"time"
)

// Function to calculate fibonacci
func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return Fibonacci(n-1) + Fibonacci(n-2)
}

// Memory holds a function and a map of results
type Memory struct {
	f     Function               // Function to be used
	cache map[int]FunctionResult // Map of results for a given key
	lock  sync.RWMutex           // Lock to protect the cache
}

// A function has to recive a value and return a value and an error
type Function func(key int) (interface{}, error)

// The result of a function
type FunctionResult struct {
	value interface{}
	err   error
}

// NewCache creates a new cache
func NewCache(f Function) *Memory {
	return &Memory{f, make(map[int]FunctionResult), sync.RWMutex{}}
}

// Get returns the value for a given key
func (m *Memory) Get(key int) (interface{}, error) {

	// Lock the cache
	m.lock.Lock()

	// Check if the value is in the cache
	res, exist := m.cache[key]

	// Unlock the cache
	m.lock.Unlock()

	// If the value is not in the cache, calculate it
	if !exist {
		m.lock.Lock()
		res.value, res.err = m.f(key) // Calculate the value
		m.cache[key] = res            // Store the value in the cache
		m.lock.Unlock()
	}

	return res.value, res.err
}

// Function to be used in the cache
func GetFibonacci(key int) (interface{}, error) {
	return Fibonacci(key), nil
}

func main() {
	empezar := time.Now()
	// Create a cache and some values
	cache := NewCache(GetFibonacci)
	values := []int{42, 40, 41, 42, 38, 41, 42}

	var wg sync.WaitGroup

	maxGoroutines := 2
	channel := make(chan int, maxGoroutines)

	// For each value to calculate, get the value and print the time it took to calculate
	for _, v := range values {

		go func(v int) {
			defer wg.Done()
			channel <- 1
			start := time.Now()

			res, err := cache.Get(v)
			if err != nil {
				fmt.Printf("Error: %v\n", err)
			}

			fmt.Printf("%v:%d took %v\n", v, res, time.Since(start))
			<-channel
		}(v)
		wg.Add(1)
	}

	wg.Wait()
	fmt.Printf("Tiempo total: %v\n", time.Since(empezar))

}

Aunque entiendo que es un objetivo didáctico para ver distintas situaciones que nos podemos encontrar con Gouroutines y como aplicar soluciones, tal y como han comentado otros compañeros el uso de gouroutines empeora el funcionamiento.
.
En este caso es absurdo realizar goroutines, ya que haciendo un sistema de cache potente, donde se guardan todos los cálculos, este proceso de cálculo se vuelve instantáneo para “cualquier” valor (podéis ver el código en mi aporte de la anterior clase).

150, 204.649µs, 6792540214324356296
42, 270ns, 267914296
40, 159ns, 102334155
41, 118ns, 165580141
42, 123ns, 267914296
38, 144ns, 39088169
50, 148ns, 12586269025
20, 94ns, 6765
60, 151ns, 1548008755920
100, 201ns, 3736710778780434371
122, 186ns, 5167068349195539697
Process completed in 290.33µs

Como podéis ver, el fibonacci de 150 lo calcula sin despeinarse. Aunque sea a modo ejemplo, también es importante que quede claro cuando aplicar una solución u otra, ya que las goroutines molan mucho, pero no son siempre aplicables. Del mismo modo que un sistema de cache no siempre es viable tal y como lo he planteado.

Hice unos cambios para que detecte que valores que no se repitan tomará para el calculo y además sea en paralelo, bloqueando sólo cuando sea necesario:
Los resultados:

calculating:  42
calculating:  41
calculating:  38
calculating:  40
38: 39088169 t: 184.896457ms
40: 102334155 t: 456.75214ms
41: 165580141 t: 729.770783ms
41: 165580141 t: 729.755414ms
42: 267914296 t: 1.172214893s
42: 267914296 t: 1.172170861s

El código:

package main

import (
	"fmt"
	"sync"
	"time"
)

// Function to calculate fibonacci
func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return Fibonacci(n-1) + Fibonacci(n-2)
}

// Memory holds a function and a map of results
type Memory struct {
	f     Function               // Function to be used
	cache map[int]FunctionResult // Map of results for a given key
	mux   sync.RWMutex
}

// A function has to recive a value and return a value and an error
type Function func(key int) (interface{}, error)

// The result of a function
type FunctionResult struct {
	value interface{}
	err   error
}

// NewCache creates a new cache
func NewCache(f Function) *Memory {
	return &Memory{f, make(map[int]FunctionResult), sync.RWMutex{}}
}

// Get returns the value for a given key
func (m *Memory) Get(key int) (interface{}, error) {
	isCalculating := false
	var value interface{}
	m.mux.Lock()
	res, exist := m.cache[key]
	if !exist {
		isCalculating = true
		m.cache[key] = FunctionResult{}
	}
	m.mux.Unlock()

	for value == nil {
		if isCalculating {
			fmt.Println("calculating: ", key)
			res.value, res.err = m.f(key) // Calculate the value
			m.mux.Lock()
			m.cache[key] = res // Store the value in the cache
			value = res.value
			m.mux.Unlock()
		} else {
			m.mux.RLock()
			res, exist = m.cache[key]
			value = res.value
			m.mux.RUnlock()
		}
	}

	return res.value, res.err
}

// Function to be used in the cache
func GetFibonacci(key int) (interface{}, error) {
	return Fibonacci(key), nil
}

func main() {
	// Create a cache and some values
	cache := NewCache(GetFibonacci)
	fibo := []int{42, 40, 41, 42, 38, 41}
	var wg sync.WaitGroup

	// For each value to calculate, get the value and print the time it took to calculate
	for _, n := range fibo {
		wg.Add(1)
		go func(index int) {
			defer wg.Done()
			start := time.Now()

			value, err := cache.Get(index)
			if err != nil {
				panic(err)
			}
			fmt.Printf("%d: %d t: %s \n", index, value, time.Since(start))
		}(n)
	}
	wg.Wait()
}

Mi versión del código para evitar que se bloquean todas los restantes cálculos cuando se está calculando 1, solo se bloquea en caso de que ya se esté trabajando con el número que queremos calcular y posteriormente usará el caché

package main

import (
	"fmt"
	"log"
	"sync"
	"time"
)

var fibs map[int]*Fib = map[int]*Fib{0: &Fib{}}

func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}

	return Fibonacci(n-1) + Fibonacci(n-2)
}

type Function func(key Fib) (interface{}, error)

type FunctionResult struct {
	value interface{}
	err   error
}

type Fib struct {
	n    int
	lock *sync.Mutex
}

func NewFib(n int) *Fib {
	flag := false
	var lock sync.Mutex
	var fib *Fib
	for k, _ := range fibs {
		if k == n {
			flag = true
			break
		}
	}

	if flag {
		fmt.Printf("Take created %d\n", n)
		fib = fibs[n]

	} else {
		fmt.Printf("Create %d\n", n)
		fib = &Fib{
			n:    n,
			lock: &lock,
		}
		fibs[n] = fib
	}

	return fib
}

func NewListFib(list ...int) []*Fib {
	var fib *Fib
	var res []*Fib
	for _, n := range list {
		fib = NewFib(n)
		res = append(res, fib)
	}
	return res
}

func (f Fib) Get(cache map[Fib]FunctionResult) FunctionResult {
	fmt.Printf("Started %d\n", f.n)
	result, exists := cache[f]

	//fmt.Println(exists)
	//fmt.Println(result)

	if !exists {
		//fmt.Println("yes")
		result.value = Fibonacci(f.n)
		result.err = nil
		cache[f] = result
	} else {
		fmt.Println("cache")
		//fmt.Println(result)
	}

	fmt.Printf("Finished %d\n", f.n)
	//fmt.Println(result)
	return result
}

type Memory struct {
	cache map[Fib]FunctionResult
}

func NewCache() *Memory {
	return &Memory{
		cache: make(map[Fib]FunctionResult),
	}
}

func (m *Memory) Get(key Fib) (interface{}, error) {
	key.lock.Lock()
	defer key.lock.Unlock()
	result := key.Get(m.cache)
	//fmt.Printf("Cache: %v\n", m.cache)
	return result.value, result.err
}

func main() {
	cache := NewCache()
	fibo := NewListFib(42, 40, 41, 42, 38)
	var wg sync.WaitGroup
	for _, n := range fibo {
		wg.Add(1)
		go func(index Fib, wg *sync.WaitGroup) {
			defer wg.Done()
			start := time.Now()
			value, err := cache.Get(index)
			if err != nil {
				log.Println(err)
			}
			fmt.Printf("%d, %s, %d\n", index, time.Since(start), value)
		}(*n, &wg)
	}
	wg.Wait()

}

Interesante