Revision - 8f5bbad - Add and benchmark alternative immset methods

Revision 8f5bbad392b904d1f5b7e9f4ee262f339d999056 authored by Damian Sawicki on 13 June 2024, 08:41:41 UTC, committed by Dylan Reimerink on 15 June 2024, 08:22:04 UTC

Add and benchmark alternative immset methods

This commit adds alternative implementations of methods of ImmSet:
 * InsertNew(xs ...T)
 * DeleteNew(xs ...T)
 * UnionNew(s2 ImmSet[T])
 * DifferenceNew(s2 ImmSet[T])
and benchmarks these implementations agains the existing ones.

Benchmarking results:
 * for Insert, the proposed method becomes faster already with the
   container of size 1000, and then it performed 10x faster for size
   10,000 and 100x faster for size 100,000;
 * for Delete, the proposed method becomes faster already with the
   container of size 1000, and then it performed ~5x faster for size
   10,000;
 * for Difference, the proposed method was already 4x faster for size
   100, and then it performed 7x faster for size 1000, 35x times faster
   for size 10,000, and 193x faster for size 100,000;
 * for Union, the proposed method performs slightly faster, but gains
   do not visibly grow with increasing size.

Theoretically, the proposed solutions have improved computational
complexity:
 * the complexity of Insert is O(len(s.xs)*len(xs)), and the complexity
   of InsertNew is O(len(s.xs)+len(xs));
 * the complexity of Delete is O(len(s.xs)*len(xs)), and the complexity
   of DeleteNew is O(len(s.xs)+len(xs));
 * the complexity of Difference is O(len(s.xs)*len(s2.xs)) because it
   uses Delete internally, and the complexity of DifferenceNew
   O(len(s.xs)+len(s2.xs));
 * the complexity of Union is harder to estimate: it involves sorting a
   slice of size n=len(s.xs)+len(s2.xs), but this slice is a
   concatenation of two sorted slices, so most likely this does not lead
   to the usual O(n*log(n)) complexity; of course, it is at least O(n);
   the complexity of UnionNew is O(n).

Signed-off-by: Damian Sawicki <dsawicki@google.com>

1 parent 5aa52b0

Files
Changes

Permalinks

Makefile.defs

# Copyright Authors of Cilium
# SPDX-License-Identifier: Apache-2.0

SHELL := /usr/bin/env bash
.SHELLFLAGS := -eu -o pipefail -c

# define a function replacing spaces with commas in a list
empty :=
space := $(empty) $(empty)
comma := ,
join-with-comma = $(subst $(space),$(comma),$(strip $1))

define newline


endef

ROOT_DIR := $(shell dirname $(realpath $(lastword $(MAKEFILE_LIST))))
RELATIVE_DIR := $(shell echo $(realpath .) | sed "s;$(ROOT_DIR)[/]*;;")
include $(ROOT_DIR)/Makefile.quiet

PREFIX?=/usr
BINDIR?=$(PREFIX)/bin
CNIBINDIR?=/opt/cni/bin
CNICONFDIR?=/etc/cni/net.d
LIBDIR?=$(PREFIX)/lib
LOCALSTATEDIR?=/var
RUNDIR?=/var/run
CONFDIR?=/etc

export GO ?= go
NATIVE_ARCH = $(shell GOARCH= $(GO) env GOARCH)
export GOARCH ?= $(NATIVE_ARCH)

INSTALL = install

CONTAINER_ENGINE?=docker
DOCKER_FLAGS?=
DOCKER_BUILD_FLAGS?=

# use gsed if available, otherwise use sed.
# gsed is needed for MacOS to make in-place replacement work correctly.
SED ?= $(if $(shell command -v gsed),gsed,sed)

# Set DOCKER_DEV_ACCOUNT with "cilium" by default
ifeq ($(DOCKER_DEV_ACCOUNT),)
    DOCKER_DEV_ACCOUNT=cilium
endif

ifneq ($(CI_BUILD),)
    DOCKER_IMAGE_SUFFIX=-ci
    DOCKER_IMAGE_TAG=$(shell git rev-parse HEAD)
endif

# Set DOCKER_IMAGE_TAG with "latest" by default
ifeq ($(DOCKER_IMAGE_TAG),)
    DOCKER_IMAGE_TAG=latest
endif

ETCD_IMAGE=gcr.io/etcd-development/etcd:v3.5.11@sha256:8eff25cf636711fb48426005b55fc9f4d6ffa4f38f483fa87c8cc82976347bbb

CONSUL_IMAGE=consul:1.7.2

CILIUM_BUILDER_IMAGE=$(shell cat $(ROOT_DIR)/images/cilium/Dockerfile | grep "ARG CILIUM_BUILDER_IMAGE=" | cut -d"=" -f2)

export CILIUM_CLI ?= cilium
export KUBECTL ?= kubectl

# Till the self-hosted renovate PR #30185 is merged, we might need to run the below
# command locally for any version update.
# make generate-api generate-health-api generate-hubble-api generate-operator-api generate-kvstoremesh-api
# renovate: datasource=docker depName=quay.io/goswagger/swagger
SWAGGER_VERSION := v0.30.5
SWAGGER := $(CONTAINER_ENGINE) run -u $(shell id -u):$(shell id -g) --rm -v $(ROOT_DIR):$(ROOT_DIR) -w $(ROOT_DIR) --entrypoint swagger quay.io/goswagger/swagger:$(SWAGGER_VERSION)

# go build/test/clean flags
# these are declared here so they are treated explicitly
# as non-immediate variables
GO_BUILD_FLAGS ?=
GO_TEST_FLAGS ?=
GO_CLEAN_FLAGS ?=
GO_BUILD_LDFLAGS ?=
# go build/test -tags values
GO_TAGS_FLAGS += osusergo

# This is declared here as it is needed to change the covermode depending on if
# RACE is specified.
GOTEST_COVER_OPTS =

# By default, just print go test output immediately to the terminal. If tparse
# is installed, use it to format the output. Use -progress instead of -follow,
# as the latter is too verbose for most of the test suite.
GOTEST_FORMATTER ?= cat
ifneq ($(shell command -v tparse),)
	GOTEST_COVER_OPTS += -json
	GOTEST_FORMATTER = tparse
ifneq ($(V),0)
	GOTEST_FORMATTER += -progress
endif
endif

# renovate: datasource=docker depName=golangci/golangci-lint
GOLANGCILINT_WANT_VERSION = v1.59.1
GOLANGCILINT_IMAGE_SHA = sha256:b5f8712114561f1e2fbe74d04ed07ddfd992768705033a6251f3c7b848eac38e
GOLANGCILINT_VERSION = $(shell golangci-lint version --format short 2>/dev/null)

VERSION = $(shell cat $(dir $(lastword $(MAKEFILE_LIST)))/VERSION)
VERSION_MAJOR = $(shell cat $(dir $(lastword $(MAKEFILE_LIST)))/VERSION | cut -d. -f1)
# Use git only if in a Git repo
ifneq ($(wildcard $(dir $(lastword $(MAKEFILE_LIST)))/.git),)
    GIT_VERSION = $(shell git show -s --format='format:%h %aI')
else
    GIT_VERSION = $(shell cat $(ROOT_DIR)/GIT_VERSION)
endif
FULL_BUILD_VERSION = $(VERSION) $(GIT_VERSION)
GO_BUILD_LDFLAGS += -X "github.com/cilium/cilium/pkg/version.ciliumVersion=$(FULL_BUILD_VERSION)"

ifeq ($(NOSTRIP),)
    # Note: these options will not remove annotations needed for stack
    # traces, so panic backtraces will still be readable.
    #
    # -w: Omit the DWARF symbol table.
    # -s: Omit the symbol table and debug information.
    GO_BUILD_LDFLAGS += -s -w
endif

ifneq ($(wildcard $(dir $(lastword $(MAKEFILE_LIST)))/images/cilium/Dockerfile),)
    CILIUM_ENVOY_REF=$(shell sed -E -e 's/^ARG CILIUM_ENVOY_IMAGE=([^ ]*)/\1/p;d' < $(ROOT_DIR)/images/cilium/Dockerfile)
    CILIUM_ENVOY_SHA=$(shell echo $(CILIUM_ENVOY_REF) | sed -E -e 's/[^/]*\/[^:]*:(.*-)?([^:@]*).*/\2/p;d')
    GO_BUILD_LDFLAGS += -X "github.com/cilium/cilium/pkg/envoy.requiredEnvoyVersionSHA=$(CILIUM_ENVOY_SHA)"
endif

# Use git only if in a Git repo, otherwise find the files from the file system
BPF_SRCFILES_IGNORE = bpf/.gitignore
ifneq ($(wildcard $(dir $(lastword $(MAKEFILE_LIST)))/.git),)
    BPF_SRCFILES := $(shell git ls-files $(ROOT_DIR)/bpf/ | LC_ALL=C sort | tr "\n" ' ')
else
    # this line has to be in-sync with bpf/.gitignore, please note usage of make patterns like `%.i`
    BPF_SRCFILES_IGNORE += bpf/%.i bpf/%.s bpf/.rebuild_all
    BPF_SRCFILES := $(shell find $(ROOT_DIR)/bpf/ -type f | LC_ALL=C sort | tr "\n" ' ')
endif

# ROOT_DIR can be either `../` or absolute path, each of these need to be stripped
BPF_SRCFILES := $(filter-out $(BPF_SRCFILES_IGNORE),$(subst ../,,$(subst $(ROOT_DIR)/,,$(BPF_SRCFILES))))

GO_BUILD_FLAGS += -mod=vendor
GO_TEST_FLAGS += -mod=vendor -vet=all
GO_CLEAN_FLAGS += -mod=vendor

GO_BUILD = CGO_ENABLED=0 $(GO) build

# Support CGO cross-compiling for amd64 and arm64 targets
CGO_CC =
CROSS_ARCH =
ifneq ($(GOARCH),$(NATIVE_ARCH))
    CROSS_ARCH = $(GOARCH)
endif
ifeq ($(CROSS_ARCH),arm64)
    CGO_CC = CC=aarch64-linux-gnu-gcc
else ifeq ($(CROSS_ARCH),amd64)
    CGO_CC = CC=x86_64-linux-gnu-gcc
endif
GO_BUILD_WITH_CGO = CGO_ENABLED=1 $(CGO_CC) $(GO) build

ifneq ($(RACE),)
    GO_BUILD_FLAGS += -race
    GO_TEST_FLAGS += -race
    GOTEST_COVER_OPTS += -covermode=atomic

    # GO_BUILD becomes GO_BUILD_WITH_CGO as `-race` requires CGO
    GO_BUILD = $(GO_BUILD_WITH_CGO)
    ifeq ($(LOCKDEBUG),)
        LOCKDEBUG=1
    endif
else
    GOTEST_COVER_OPTS += -covermode=count
endif

ifneq ($(LOCKDEBUG),)
    GO_TAGS_FLAGS += lockdebug
endif

GO_BUILD_FLAGS += -ldflags '$(GO_BUILD_LDFLAGS) $(EXTRA_GO_BUILD_LDFLAGS)' -tags=$(call join-with-comma,$(GO_TAGS_FLAGS)) $(EXTRA_GO_BUILD_FLAGS)
GO_TEST_FLAGS += -tags=$(call join-with-comma,$(GO_TAGS_FLAGS))

ifeq ($(NOOPT),1)
    GO_BUILD_FLAGS += -gcflags="all=-N -l"
endif

GO_BUILD += $(GO_BUILD_FLAGS)
GO_BUILD_WITH_CGO += $(GO_BUILD_FLAGS)

GO_TEST = CGO_ENABLED=0 $(GO) test $(GO_TEST_FLAGS)
GO_CLEAN = $(GO) clean $(GO_CLEAN_FLAGS)

GO_VET = $(GO) vet
GO_LIST = $(GO) list

HELM_TOOLBOX_VERSION ?= "v1.1.0"
HELM_TOOLBOX_SHA ?= "961693f182b9b456ed90e5274ac5df81e4af4343104e252666959cdf9570ce9e"
HELM_TOOLBOX_IMAGE ?= "quay.io/cilium/helm-toolbox:$(HELM_TOOLBOX_VERSION)@sha256:$(HELM_TOOLBOX_SHA)"

YQ_VERSION ?= "4.40.5"
YQ_SHA ?= "32be61dc94d0acc44f513ba69d0fc05f1f92c2e760491f2a27e11fc13cde6327"
YQ_IMAGE ?= "mikefarah/yq:$(YQ_VERSION)@sha256:$(YQ_SHA)"

define print_help_line
  @printf "  \033[36m%-29s\033[0m %s.\n" $(1) $(2)
endef

define print_help_from_makefile
  @awk 'BEGIN {FS = ":.*##"; printf "\nUsage:\n  make \033[36m<target>\033[0m\n"} /^[a-zA-Z0-9][a-zA-Z0-9 _-]*:.*?##/ { split($$1, targets, " "); for (i in targets) { printf "  \033[36m%-28s\033[0m %s\n", targets[i], $$2 } } /^##@/ { printf "\n\033[1m%s\033[0m\n", substr($$0, 5) } ' $(MAKEFILE_LIST)
endef

# Use to ensure the CWD, or any child of it, belongs to Cilium's go module.
CILIUM_GO_MODULE = github.com/cilium/cilium
CURRENT_GO_MODULE = $(shell go list -m)
define ASSERT_CILIUM_MODULE
	$(if $(filter $(CILIUM_GO_MODULE), $(CURRENT_GO_MODULE)) ,, $(error "Could not locate Cilium's go.mod file, are you in Cilium's repository?"))
endef

Showing with 0 additions and 0 deletions (0 / 0 diffs computed)

Computing file changes ...