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
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
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
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...