ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
25 сообщений из 227, страница 4 из 10
  4  все
Тяпничная унификация
    #39516025
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Сведенья по тестовым данным.

md5Filesize8e32018f35dde63bcb347e8ad4456305ripe.db5 462 799 419a7d47a1ebed601c4c9c2df7cc85f74aehashkiller-dict.txt1 237 341 935

Чуть позже я сделаю enrichment этих данных чтоб добавить кардинальность и количество строк.
...
Рейтинг: 0 / 0
05.09.2017, 21:46
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516027
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, спрасибо. Статистика хорошая.

По поводу сорца.
Код: plaintext
1.
2.
3.
4.
5.
while (fgets(buf, sizeof(buf), f) != NULL) {
#endif
				size_t len = strlen(buf);
				//uniq_total += len;
				crc32_t crc = crc32(buf, len);


Я не знаю как устрена твоя функция crc32 но КМК мы сжигаем полезные мегафлопы
на расчете strlen. Можно было объединить это всесте с crc32. А результаты вернуть по ссылкам.
...
Рейтинг: 0 / 0
05.09.2017, 21:49
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516036
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
 
Старые проекты такие как primegen-experiments, Card-raytracer-benchmark никуда не пропали
просто я тихонько мигрирую на гитхаб. Так что все сорцы сохранились.

Я пытаюсь исследовать возможности github и bitbucket и выбрать что удобнее.
GitHub не позволяет скрыть исходники (по крайней мере бесплатно). И это
минус который заставляет меня искать другие планы хостинга.
...
Рейтинг: 0 / 0
05.09.2017, 22:15
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516132
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.
Еле нашел кем там числюсь: dmitriyt

Посмотри в этом проекте, в настройках может остались кто учавствовал: https://sourceforge.net/projects/card-raytracer-bench/
...
Рейтинг: 0 / 0
06.09.2017, 08:45
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516134
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.Учетка аналогичная, письмо через сорсфордж отправлял.
добавь к проекту обсуждения или тикеты, можно было бы там отписываться.

битбукетом пользуюсь для личных коммерческих проектов
...
Рейтинг: 0 / 0
06.09.2017, 08:48
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516140
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Добавил обоих.
...
Рейтинг: 0 / 0
06.09.2017, 08:59
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516145
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ не знаю как устрена твоя функция crc32 но КМК мы сжигаем полезные мегафлопы
на расчете strlen. Можно было объединить это всесте с crc32. А результаты вернуть по ссылкам.
 
crc32() где-то в инете нашел
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
#pragma once
#include <stdint.h>
#include <stdlib.h> 
#define CRCPOLY 0xEDB88320

typedef uint32_t crc32_t;

// Инициализация таблицы
static crc32_t* crc32_init() noexcept {
	crc32_t* crc_tab = (crc32_t*)malloc(256 * sizeof(crc32_t));
	if (crc_tab != NULL) {
		// Заполнение таблицы
		for (crc32_t i = 0; i < 256; i++) {
			crc32_t c = i;
			for (crc32_t j = 0; j < 8; j++) {
				if ((c & 1) != 0) {
					c = CRCPOLY ^ (c >> 1);
				}
				else {
					c = c >> 1;
				}
			}
			crc_tab[i] = c;
		}
	}
	return crc_tab;
}

// Расчет CRC32 блока памяти. prev_crc32 результат предыдущего блока
crc32_t crc32(const void* data, size_t size, crc32_t prev_crc32 = 0) noexcept {
	static crc32_t* crc_tab = NULL;
	if (crc_tab == NULL) {
		crc_tab = crc32_init();
	}
	else if (size == 0 && crc_tab != NULL) {
		free(crc_tab);
		crc_tab = NULL;
	}
	// Расчет
	prev_crc32 ^= 0xffffffff;
	if (crc_tab != NULL) {
		const uint8_t* buf = (uint8_t*)data;
		for (size_t i = 0; i < size; i++) {
			prev_crc32 = (prev_crc32 >> 8) ^ crc_tab[(prev_crc32 & 0xFF) ^ *buf];
			buf++;
		}
	}
	return prev_crc32 ^= 0xffffffff;
}


Если тут что-то менять, то fgets() на fread() или вообще WinAPI задействовать, т.е. читать страницами кратно секторам.
Я замеры делал: fgets() 60% времени съедает. Просто прочитать файл (5.2 Гб) с подсчетом кол-во строк: 26 сек. с добавлением strlen() и crc32() 44 сек. Т.е. чисто чтение 200 Мб/сек, хотя файл лежал на SSD с чтением 700 МБ/сек, а может вообще в кэше виндовса.

В общем надо чтение ускорять, потом можно акторы добавить и расчет crc32 распараллелить :)

Попозже соберу исходники в отдельный проект. На скорую руку писал в проекте для тестов, там помойка из всякой всячины.
...
Рейтинг: 0 / 0
06.09.2017, 09:08
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516148
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я-бы предложил пока без акторов. Но отказаться от строковых операций
и сделать работу на базе fopen/fread. Тоесть работать с потоком байт(символов).
...
Рейтинг: 0 / 0
06.09.2017, 09:13
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516154
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.
Еле нашел кем там числюсь: dmitriyt

Посмотри в этом проекте, в настройках может остались кто учавствовал: https://sourceforge.net/projects/card-raytracer-bench/
Я тогда посчитал что коммитов больше не будет и
поудалял участников и списка девелоперов.

Поскольку я больше сабжем не занимался то и
просматривать changes мне уже не хотелось.

Лишняя обязанность была ни к чему. Но я могу
возобновить активности по Card-Raytrace если
будут предложения от мемберов.
...
Рейтинг: 0 / 0
06.09.2017, 09:23
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516215
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonДобавил обоих.закоммитил
...
Рейтинг: 0 / 0
06.09.2017, 10:25
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516275
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Siemargl,

Oh! Thnx.
...
Рейтинг: 0 / 0
06.09.2017, 11:26
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516803
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По поводу своего сорца. Я до него доберусь не раньше выходных (я так думаю).

Дима. Не видел пока еще твоего коммита. Размышлял по поводу worst-case. Я думаю если объединить
файл сам с собой через cat, то мы как раз получим этот самый случай.

Siemargl. Интересный алгоритм. Насколько я понял предлагается использовать сам файл как хранилище
искомых строк. У меня возникает вопрос дисковой нагрузки. Надо сделать бенчмарк чтобы посмотреть
насколько это дорогая операция.

По поводу всех (в будущем) алгоритмов. Я не ищу лучшего. Я буду строить матрицу алгоритмов
где каждый имеет свои сильные стороны. Для каждого файла (для каждого распределения данных)
будет оптимальным какой-то определенный алгоритм и (возможно) с кастомным вектором парамтеров.

В настоящий момент я уже выделяю их столько:

1) Naive Hash-table.(NHT) Это самая первая наивная идея о которой думал каждый разработчик. И которая возможно
нелетает вследствие некоторого соотношения cardinality/rows. Но она тоже участвует в гонке.
2) CRC32-2-Phase . Вариант Димы.
3) Big-File-Unique-Lines-Counting (BFULC) . Вариант Зямы.
4) Split-Bucket-Processing-2-Phase (SBP2P) . Мой вариант который я еще не осилил.
5) Linux-Sort-Unique (LSU) . Куда-ж без него (машу Дохтару рукой).

Если есть еще варианты - пишите. Прошу также коммитить работающий код.

Илья? Сова? Вас тоже приглашаю.
...
Рейтинг: 0 / 0
06.09.2017, 21:56
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516808
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

если хэш адекватный размеру исходников (64бит для 5Гб хватает), то перепроверка не требуется, иначе удесятеряет/вниз скорость

я могу ускорить перепроверку, введя кэш LFU, но честно говоря, возник вопрос - а какая точность решения задачи допустима?
...
Рейтинг: 0 / 0
06.09.2017, 22:18
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516809
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нужно точное решение. Боюсь что приближенное просто никому не будет нужно.
...
Рейтинг: 0 / 0
06.09.2017, 22:26
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516811
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Обновлённые сведенья по тестовым выборкам.

md5FileSizeRowsCardinalityCard/RowsAvgRowLenc4095f84f8f0e20fc15e85108face730edit_data27G43 891 6806608e32018f35dde63bcb347e8ad4456305ripe.db5 462 799 419143 410 60438a7d47a1ebed601c4c9c2df7cc85f74aehashkiller-dict.txt1 237 341 93588 405 43013
Некоторые колонки я еще не посчитал. Сорян. Нечем
...
Рейтинг: 0 / 0
06.09.2017, 22:35
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516825
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

ждем твое решение на яве
...
Рейтинг: 0 / 0
06.09.2017, 23:06
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516830
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Данную тулзу я напишу на сях.
...
Рейтинг: 0 / 0
06.09.2017, 23:18
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516833
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Дима. Я посмотрел на этот кусок функции и возникла мысль что не стоит так часто
очищать полезную таблицу магических констант для CRC32. Пускай она живет все
время пока работает приложение. ИМХО.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
// Расчет CRC32 блока памяти. prev_crc32 результат предыдущего блока
crc32_t crc32(const void* data, size_t size, crc32_t prev_crc32 = 0) noexcept {
	static crc32_t* crc_tab = NULL;
	if (crc_tab == NULL) {
		crc_tab = crc32_init();
	}
	else if (size == 0 && crc_tab != NULL) {
		free(crc_tab);
		crc_tab = NULL;
	}
	// Расчет


[/SRC]
...
Рейтинг: 0 / 0
06.09.2017, 23:29
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516852
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Siemargl, запустил твоё приложение под Windows10-x64/MinGW-6.4.0.
Анализировал hashkiller-dict.txt.
Где-то после 8 минут работы - прервал. Скушал доступную память
(где-то с 4Г занятых у меня до 7.9). При этом в консоли было
Completed 940 Mb.

Вобщем надо что-то подоптимизировать. Это был самый мелкий файл
из моей тестовой выборки.
...
Рейтинг: 0 / 0
07.09.2017, 00:19
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516891
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима. Я посмотрел на этот кусок функции и возникла мысль что не стоит так часто
очищать полезную таблицу магических констант для CRC32. Пускай она живет все
время пока работает приложение. ИМХО.
Это было задумано для освобождения памяти, т.к. незачем считать CRC от блока в 0 байт, но в нашем случае встречаются пустые строки, где size == 0.
Закаментил, затестил, на 5 сек быстрее стало чем 20773604 :

Код: plaintext
Time 152806 ms. Total unique 26511499 rows.
...
Рейтинг: 0 / 0
07.09.2017, 07:35
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516898
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима. Не видел пока еще твоего коммита.
Вчера вечером пытался заменить fgets() на fread(), запутался в поисках конца последней полной строки: указатели, смещения ... (((
Сегодня оформлю в отдельный проект вариант с fgets(), залью.
maytonРазмышлял по поводу worst-case. Я думаю если объединить
файл сам с собой через cat, то мы как раз получим этот самый случай.
Да, так и есть. На перепроверку во втором проходе пойдут все уникальные найденные по CRC.
...
Рейтинг: 0 / 0
07.09.2017, 07:48
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516899
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, может стрельнуть последовательность чередующихся пустых строк.
...
Рейтинг: 0 / 0
07.09.2017, 07:51
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516903
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonпод Windows10-x64/MinGW-6.4.0.
Ты компилятор обновил? С++11 понимает?

Помня что у тебя акторы не скомпилировались, не стал unordered_map и unordered_set использовать. Они немного побыстрее чем map и set.
...
Рейтинг: 0 / 0
07.09.2017, 07:59
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516904
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonSiemargl, запустил твоё приложение под Windows10-x64/MinGW-6.4.0.
Анализировал hashkiller-dict.txt.
Где-то после 8 минут работы - прервал. Скушал доступную память
(где-то с 4Г занятых у меня до 7.9). При этом в консоли было
Completed 940 Mb.

Вобщем надо что-то подоптимизировать. Это был самый мелкий файл
из моей тестовой выборки.У меня такого файла нет. Выкладывай ссылки на входные данные.
...
Рейтинг: 0 / 0
07.09.2017, 08:00
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39516905
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TВчера вечером пытался заменить fgets() на fread(), запутался в поисках конца последней полной строки: указатели, смещения ... (((
Сегодня оформлю в отдельный проект вариант с fgets(), залью.
ОК. Закоммить стабильную версию с fgets(). Я буду смотреть.
Мне уже хочется что-то с чем-то сравнивать.
...
Рейтинг: 0 / 0
07.09.2017, 08:00
| Ответить | Цитировать | Написать  
25 сообщений из 227, страница 4 из 10
  4  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]