From 7ec1e1332e7d04e74451acef18b41f389722b698 Mon Sep 17 00:00:00 2001
From: kim <89579420+NyaaaWhatsUpDoc@users.noreply.github.com>
Date: Fri, 19 Jan 2024 12:57:29 +0000
Subject: [performance] overhaul struct (+ result) caching library for
simplicity, performance and multiple-result lookups (#2535)
* rewrite cache library as codeberg.org/gruf/go-structr, implement in gotosocial
* use actual go-structr release version (not just commit hash)
* revert go toolchain changes (damn you go for auto changing this)
* fix go mod woes
* ensure %w is used in calls to errs.Appendf()
* fix error checking
* fix possible panic
* remove unnecessary start/stop functions, move to main Cache{} struct, add note regarding which caches require start/stop
* fix copy-paste artifact... :innocent:
* fix all comment copy-paste artifacts
* remove dropID() function, now we can just use slices.DeleteFunc()
* use util.Deduplicate() instead of collate(), move collate to util
* move orderByIDs() to util package and "generify"
* add a util.DeleteIf() function, use this to delete entries on failed population
* use slices.DeleteFunc() instead of util.DeleteIf() (i had the logic mixed up in my head somehow lol)
* add note about how collate differs from deduplicate
---
internal/util/deduplicate.go | 63 --------------------
internal/util/slices.go | 135 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 135 insertions(+), 63 deletions(-)
delete mode 100644 internal/util/deduplicate.go
create mode 100644 internal/util/slices.go
(limited to 'internal/util')
diff --git a/internal/util/deduplicate.go b/internal/util/deduplicate.go
deleted file mode 100644
index 099ec96b5..000000000
--- a/internal/util/deduplicate.go
+++ /dev/null
@@ -1,63 +0,0 @@
-// GoToSocial
-// Copyright (C) GoToSocial Authors admin@gotosocial.org
-// SPDX-License-Identifier: AGPL-3.0-or-later
-//
-// This program is free software: you can redistribute it and/or modify
-// it under the terms of the GNU Affero General Public License as published by
-// the Free Software Foundation, either version 3 of the License, or
-// (at your option) any later version.
-//
-// This program is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU Affero General Public License for more details.
-//
-// You should have received a copy of the GNU Affero General Public License
-// along with this program. If not, see .
-
-package util
-
-// Deduplicate deduplicates entries in the given slice.
-func Deduplicate[T comparable](in []T) []T {
- var (
- inL = len(in)
- unique = make(map[T]struct{}, inL)
- deduped = make([]T, 0, inL)
- )
-
- for _, v := range in {
- if _, ok := unique[v]; ok {
- // Already have this.
- continue
- }
-
- unique[v] = struct{}{}
- deduped = append(deduped, v)
- }
-
- return deduped
-}
-
-// DeduplicateFunc deduplicates entries in the given
-// slice, using the result of key() to gauge uniqueness.
-func DeduplicateFunc[T any, C comparable](in []T, key func(v T) C) []T {
- var (
- inL = len(in)
- unique = make(map[C]struct{}, inL)
- deduped = make([]T, 0, inL)
- )
-
- for _, v := range in {
- k := key(v)
-
- if _, ok := unique[k]; ok {
- // Already have this.
- continue
- }
-
- unique[k] = struct{}{}
- deduped = append(deduped, v)
- }
-
- return deduped
-}
diff --git a/internal/util/slices.go b/internal/util/slices.go
new file mode 100644
index 000000000..51d560dbd
--- /dev/null
+++ b/internal/util/slices.go
@@ -0,0 +1,135 @@
+// GoToSocial
+// Copyright (C) GoToSocial Authors admin@gotosocial.org
+// SPDX-License-Identifier: AGPL-3.0-or-later
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Affero General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Affero General Public License for more details.
+//
+// You should have received a copy of the GNU Affero General Public License
+// along with this program. If not, see .
+
+package util
+
+// Deduplicate deduplicates entries in the given slice.
+func Deduplicate[T comparable](in []T) []T {
+ var (
+ inL = len(in)
+ unique = make(map[T]struct{}, inL)
+ deduped = make([]T, 0, inL)
+ )
+
+ for _, v := range in {
+ if _, ok := unique[v]; ok {
+ // Already have this.
+ continue
+ }
+
+ unique[v] = struct{}{}
+ deduped = append(deduped, v)
+ }
+
+ return deduped
+}
+
+// DeduplicateFunc deduplicates entries in the given
+// slice, using the result of key() to gauge uniqueness.
+func DeduplicateFunc[T any, C comparable](in []T, key func(v T) C) []T {
+ var (
+ inL = len(in)
+ unique = make(map[C]struct{}, inL)
+ deduped = make([]T, 0, inL)
+ )
+
+ for _, v := range in {
+ k := key(v)
+
+ if _, ok := unique[k]; ok {
+ // Already have this.
+ continue
+ }
+
+ unique[k] = struct{}{}
+ deduped = append(deduped, v)
+ }
+
+ return deduped
+}
+
+// Collate will collect the values of type K from input type []T,
+// passing each item to 'get' and deduplicating the end result.
+// Compared to Deduplicate() this returns []K, NOT input type []T.
+func Collate[T any, K comparable](in []T, get func(T) K) []K {
+ ks := make([]K, 0, len(in))
+ km := make(map[K]struct{}, len(in))
+
+ for i := 0; i < len(in); i++ {
+ // Get next k.
+ k := get(in[i])
+
+ if _, ok := km[k]; !ok {
+ // New value, add
+ // to map + slice.
+ ks = append(ks, k)
+ km[k] = struct{}{}
+ }
+ }
+
+ return ks
+}
+
+// OrderBy orders a slice of given type by the provided alternative slice of comparable type.
+func OrderBy[T any, K comparable](in []T, keys []K, key func(T) K) {
+ var (
+ start int
+ offset int
+ )
+
+ for i := 0; i < len(keys); i++ {
+ var (
+ // key at index.
+ k = keys[i]
+
+ // sentinel
+ // idx value.
+ idx = -1
+ )
+
+ // Look for model with key in slice.
+ for j := start; j < len(in); j++ {
+ if key(in[j]) == k {
+ idx = j
+ break
+ }
+ }
+
+ if idx == -1 {
+ // model with key
+ // was not found.
+ offset++
+ continue
+ }
+
+ // Update
+ // start
+ start++
+
+ // Expected ID index.
+ exp := i - offset
+
+ if idx == exp {
+ // Model is in expected
+ // location, keep going.
+ continue
+ }
+
+ // Swap models at current and expected.
+ in[idx], in[exp] = in[exp], in[idx]
+ }
+}
--
cgit v1.2.3