Комментарии 52
Так изначальный код на питоне считал в один поток, я правильно понял листинг?
Можно, но 20 секунд и 2 дня — это не 100 раз.
Даже не 1000, а ближе к 10k, что намекает, что не в CPU дело.
Мне в аналогичой ситуации очень помог HNSW (было на Хабре: https://habr.com/en/company/mailru/blog/338360/), позиций было порядка 10^6, около 5000 признаков. Индекс строился около суток, но поиск потом был очень быстрым (и, более того, настраиваемо быстрым в обмен на качество). Формально корректные результаты, правда, были так себе, потому что исходные данные были так себе.
Там много такого. Он бы мог сразу отнормировать свои вектора вместо того, чтобы в цикле каждый раз нормировать. А по нормированным векторам можно сразу вычислять матрицу косинусных дистанций хорошо оптимизированным матричным умножением.
Но сам посыл статьи эти ляпы не отменяют.
Прочитал ваш комментарий еще раз — вы как раз и имели ввиду под пересчетом длины векторов нормировку.
А карточка уже была своя или ее специально для задачи фирма купила или в облаке использовали? Ценник не так что бы дружелюбен для «купить что бы попробовать».
Этими алгоритмами можно пользоваться только если функция расстояния является метрикой, по крайней мере должно выполняться неравенство треугольника. Скалярное произведение (делённое на длины векторов) этому не удовлетворяет, например на двумерных векторах (0, 1), (0.5, 1), (0.5, 0). Если бы автор взял функцию, являющуюся метрикой, то действительно можно было бы обойтись без GPU.
Не просто монотонно, а линейно, то есть можно без особых проблем перевести одно в другое.
Код был хорошо оптимизирован с применением операций и массивов Numpy. Отмечу, что все эти операции последовательно выполняются на CPU.
Скалярное произведение на 64 признака — numpy, двойной цикл по 105 индексов — на питоне, код хорошо оптимизирован, да.
Сдаётся, что с JIT-компиляцией без GPU вполне бы решалось всё за несколько десятков секунд, а автор в своём восхвалении либо лукавит, либо реально не понимает, в чём там дело.
И отличие между CPU и GPU при этом будет на более десяти раз.
К сожалению, матрица 10^5 на 10^5 чисел с плавающей запятой будет занимать около 80 ГБ, так что просто перемножить матрицы нельзя.
И сколько же тогда займёт перемножение, если данные будут постоянно дёргаться с диска?
"Программист на Фортране на любом языке может писать на Фортране".
У меня максимально "влобным" и неэффективным подходом без JITa ушло 20 сек на 10^4 элементов (то есть где-то в 60 раз быстрее, чем у автора). Цикл for в distance_func тривиально параллелизируется, то есть если есть CPU на ~30 потоков (или какой там Тредриппер можно купить за цену одной Вольты), то никаких "двух суток" и близко не нужно.
items = np.random.randint(1, 1000, size=(10**4, 64))
# normalize
items_norm = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
def three_closest(X, item) -> (int, int, int):
distances = np.sum(X[item, :] * X, axis=1)
first = np.argmax(distances)
distances[first] = 0
second = np.argmax(distances)
distances[second] = 0
third = np.argmax(distances)
distances[third] = 0
return first, second, third
def distance_func(X):
all_items = {}
for i in range(len(X)):
all_items[i] = three_closest(X, i)
return all_items
distance_func(items_norm)
-
Показательная статья как делать не надо.
Код мало того что не "хорошо оптимизирован", он вообще написан ужасно с точки зрения производительности. Одно и тоже вычисляется в цикле несколько раз и т.д. и т.п.
Не нужно использовать циклы для работы с матрицами. Все современные процессоры давно поддерживают Advanced Vector Extensions, которые позволяют существенно ускорить работу с матрицами.
Если уж в статье упоминается про NumPy, то именно её и надо было использовать для вычислений. Под капотом она использует высокооптимизированный код, написанный на C, и, насколько я знаю, используется тот самый AVX. Все можно было свести к паре строчек кода и работало бы оно максимум раз в 10-15 медленее чем на видеокарте.
Ну и как написали выше, есть более быстрые алгоритмы.
Также хочется отметить, число колонок 59 — очень неудачное. Если добавить ещё 5 (например, нулевых) до 64, то выполняться на gpu будет быстрее примерно в два раза.
И, конечно, стоило бы воспользоваться готовой библиотекой для этой задачи. Например, при помощи faiss те же 10^5 векторов можно обработать за 25 секунд на TR 1920x (против 50 секунд для кода из статьи на 1080Ti). Результаты совпадают.
import numpy as np
import faiss
n = 10**5
k = 59
batch_size = 18
items = np.random.rand(n, k).astype(np.float32)
items = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
bounds = np.linspace(0, n, n // batch_size + 1, dtype=np.int64)
index = faiss.IndexFlatIP(59)
index.add(items)
distance = np.zeros((n, 4), dtype=np.float32)
index_val = np.zeros((n, 4), dtype=np.int64)
for lower, upper in zip(bounds[:-1], bounds[1:]):
distance[lower:upper], index_val[lower:upper] = index.search(items[lower:upper], 4)
assert np.sum(index_val[:, 0] != np.arange(n)) == 0
distance = distance[:, 1:]
index_val = index_val[:, 1:]
import torch
n = 10**5
k = 59
batch_size = 10**3
device = 'cuda:0' # 'cpu'
nn_number = 3
items = np.random.rand(n, k).astype(np.float32)
items = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
def three_closest(X, indices):
sample_n = indices.shape[0]
index = torch.zeros((sample_n, nn_number), dtype=torch.int64, device=device)
distances = X[indices, :] @ X.T
ind_range = torch.arange(sample_n, device=device)
distances[ind_range, indices] = 0
for j in range(nn_number):
max_index = torch.argmax(distances, dim=1)
index[:, j] = max_index
distances[ind_range, max_index] = 0
return index
def distance_func(X):
X = torch.from_numpy(X).to(device=device)
all_items = torch.zeros((n, nn_number), dtype=torch.int64, device=device)
for indices in torch.split(torch.arange(n, device=device), batch_size):
all_items[indices] = three_closest(X, indices)
return all_items.cpu().numpy()
nearest_torch = distance_func(items)
нвидия, это же какой-то каменный век.
Intel Core i5-6440HQ CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 4 physical cores
.NET Core SDK=2.2.110
[Host] : .NET Core 2.2.8 (CoreCLR 4.6.28207.03, CoreFX 4.6.28208.02), X64 RyuJIT
DefaultJob : .NET Core 2.2.8 (CoreCLR 4.6.28207.03, CoreFX 4.6.28208.02), X64 RyuJITДля 100_000: 6 мин,
если преждевременно нормализировать данные 2 мин.
Загрузил все ядра процессора, плюс использовал SIMD.
Учитывая стоимость видяшки, не такой большой прирост получился
Как GPU-вычисления буквально спасли меня на работе. Пример на Python