prollytree_test.go

package prollytree

import (
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"testing"
	"time"
)

const (
	iterations         = 5
	msg_size_creation  = 100_000
	msg_size_insertion = 200_000
)

func BenchmarkProllyTreeCreationRandom(b *testing.B) {

	var durations []time.Duration
	// Reset the timer and run the benchmarks sequentially in the same loop
	b.ResetTimer()
	for i := 0; i < iterations; i++ {
		duration := treeBenchmarkCreation()
		durations = append(durations, duration)
	}

	min, max, avg, std := calculateStats(durations)
	fmt.Println("| Operation                       | Iterations | Min Time (ms) | Max Time (ms) | Avg Time (ms) | Std Dev (ms) | Ops/s      |")
	fmt.Println("|---------------------------------|------------|---------------|---------------|---------------|--------------|------------|")

	fmt.Printf("| %-30s | %10d | %10.4f | %10.4f | %10.4f | %10.4f | %10d |\n",
		"Create random 100k entries", iterations, min.Seconds()*1000, max.Seconds()*1000, avg.Seconds()*1000, std.Seconds()*1000, int64(float64(1)/avg.Seconds()))
}

func BenchmarkProllyTreeInsertionRandom(b *testing.B) {

	var durations []time.Duration
	// Reset the timer and run the benchmarks sequentially in the same loop
	b.ResetTimer()
	for i := 0; i < iterations; i++ {
		duration := treeBenchmarkInsertion()
		durations = append(durations, duration)
	}

	min, max, avg, std := calculateStats(durations)
	fmt.Println("| Operation                       | Iterations | Min Time (ms) | Max Time (ms) | Avg Time (ms) | Std Dev (ms) | Ops/s      |")
	fmt.Println("|---------------------------------|------------|---------------|---------------|---------------|--------------|------------|")

	fmt.Printf("| %-30s | %10d | %10.4f | %10.4f | %10.4f | %10.4f | %10d |\n",
		"Insert random 100k entries", iterations, min.Seconds()*1000, max.Seconds()*1000, avg.Seconds()*1000, std.Seconds()*1000, int64(float64(1)/avg.Seconds()))
}

func treeBenchmarkCreation() time.Duration {
	startTime := time.Now()
	messages := make([]*Message, msg_size_creation)
	for i := 0; i < msg_size_creation; i++ {
		messages[i] = NewMessage(strconv.Itoa(i), i)
	}

	// Shuffle messages to simulate the random order
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(messages), func(i, j int) {
		messages[i], messages[j] = messages[j], messages[i]
	})

	// Tree creation benchmark
	_ = NewProllyTree(messages)

	duration := time.Since(startTime)

	return duration

}

func treeBenchmarkInsertion() time.Duration {
	// Prepare messages before benchmarking to exclude the preparation time
	messages := make([]*Message, msg_size_insertion)
	for i := 0; i < msg_size_insertion; i++ {
		messages[i] = NewMessage(strconv.Itoa(i), i)
	}

	// Shuffle messages to simulate the random order
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(messages), func(i, j int) {
		messages[i], messages[j] = messages[j], messages[i]
	})

	halfSize := msg_size_insertion / 2
	firstHalf := messages[:halfSize]
	secondHalf := messages[halfSize:]

	// Tree creation benchmark
	tree := NewProllyTree(firstHalf)

	// Tree insertion benchmark
	startTime := time.Now()
	for _, message := range secondHalf {
		tree.Insert(message)
	}
	duration := time.Since(startTime)

	return duration

}

// calculateStats computes the statistical metrics for the benchmark results
func calculateStats(durations []time.Duration) (min, max, avg, std time.Duration) {
	sum := 0.0
	min = time.Duration(1<<63 - 1)
	max = time.Duration(0)

	for _, d := range durations {
		durationSec := d.Seconds() * 1000 // Convert duration to milliseconds
		sum += durationSec
		if d < min {
			min = d
		}
		if d > max {
			max = d
		}
	}

	avg = time.Duration(sum/float64(len(durations))) * time.Millisecond

	// Calculate standard deviation
	var varianceSum float64
	for _, d := range durations {
		durationSec := d.Seconds() * 1000 // Convert duration to milliseconds
		variance := durationSec - avg.Seconds()*1000
		varianceSum += variance * variance
	}
	variance := varianceSum / float64(len(durations))
	std = time.Duration(math.Sqrt(variance)) * time.Millisecond

	return
}