LINUX.ORG.RU
 
siberean

Вау, джава не медленнее Си на обработке больших текстовых массивов


0

3

Только что портил некоторые тулзы, обрабатывающие генетическую информацию с ANSI C на джаву, строка-в-строку.
И был очень удивлён, что разница - в пределах ошибки.
Тулзы типа транспонируют матрицы, ну просто крутят данные, а данных могут быть многие гигабайты. Только одна строка - порядка миллиона аллелей, а их может быть много.
Дык вот, на Си, скажем, миллион рекордов обрабатывается в 1.5-1.8 секунд. На джаве - 2.5 секунд вместе с загрузкой виртуальной машины, но саму строку обрабатывает 1.8 секунд (колеблется в приделах 20% в моём ленивом семпле из 5 запусков). Т.е. когда количество строк будет очень большим - загрузкой VM можно пренебречь, а данные колошматят как Си (gcc -O2) и джава - с одинаковой скоростью.

Детали: маллоками не пользуюсь, всё делаю на стеке. В джаве тоже всё в стиле Си (немногие классы - как сишные структуры с публичным доступом - на частые операции, в основном - функции). Никакого юникода (его в тех форматах не предвидится), поэтому читаю асками, как intы и кастю в char под конец, только что нужно. Т.е. оптимизированнее некуда.

Этак можно на Си забить для подобных задач (я давно тестил одну и ту же большую экстракцию данных из базы - разницы не заметил, но там ясно: чистое ожидание IO, в базах на Си давно забил. Потом тестил хэши, работа с большимы хешами также в джаве оказалась даже быстрее). А тут такое. С большими локальными файлами и их обработке. Однако...

НАУЧИ КОМПЬЮТЕР ВАРИТЬ КОФЕ

управление электрическими цепями с помощью компьютера
лучший подарок для техногика; только открытые программы
http://www.unicontrollers.com/products/unc01x

[#] Ответ на: комментарий от DNA_Seq 30.04.2011 11:48:05  
siberean

> Те кто в теме поймут. Правда они обычно прекрасно в курсе что подобное лучше на перле писать

может поэтому не некоторых сайтах пишут, типа: "мы ранним батч процесс, приходите через 3 дня".

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

* ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:24:59  
sergej

Если предположить, что ява вм и библиотеки jni собраны тем же компилятором, что и приложение на си, то всё не так уж плохо.

***** ()
[#] Ответ на: комментарий от segfault 30.04.2011 13:26:05  
siberean

ну я пробовал алгоритм Бернштейна, sdbm, алгоритм беркли ДБ используя свои простые структуры.
Там нечего буферизовать, всё и так в памяти, а полиномы простые, эффективнее вроде уже не напишешь, умножения все через сдвиги.

И пробовал B+tree ("красно-чёрные деревья", в терминах Кнута?) джавовский, получилось быстрее.

http://siberean.livejournal.com/2253.html

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 17:56:04  
DNA_Seq

> (пока в строке под миллион аллелей а в будущем может быть до 2х и может и больше)

случайно не SNP-чипы анализируются? Больше вспомнить не могу где подобный объем данных единовременно может быть. Чем тогда bioconductor не устраивает?

*** ()
[#] Ответ на: комментарий от sergej 30.04.2011 18:31:53  
DNA_Seq

>Если предположить, что ява вм и библиотеки jni собраны тем же компилятором, что и приложение на си, то всё не так уж плохо.

Это предположение ничем не обосновано. Вот PyPy быстрее интерпретатора питона на си работает, угадай почему

*** ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:25:24  
DNA_Seq

>но он ведь читает строками, не?

может работать с текстовыми файлами как с бинарными - читать/писать через буфер. Другое дело что на числодробилке он будет на порядок медленнее

*** ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:40:06  
sergej

Наверное из-за jit. В любом случае пункт 3 о компиляторах очень маловероятен. В самом худшем случае обычно можно сменить компилятор.

***** ()
[#] Ответ на: комментарий от sergej 30.04.2011 18:44:29  
DNA_Seq

>Наверное из-за jit.

ЕМНИП там жита нет

>В самом худшем случае обычно можно сменить компилятор.


В си??? Попробуй собрать ведро компилятором отличным от gcc

*** ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:37:30  
siberean

Из последнего я понял, что джава не так уж и плоха. Это просто то что на ней сейчас вытворяют - так ужасно. Грузят всё в память, получают конечно OutOfMemory, аллоцируют изначально виртуалке по гигабайту. А если ту же машину состояний писать на джаве и думать над алгоритмом - получается не так и плохо. И встроенные мапы не плохо реализованы.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:45:52  

> Из последнего я понял, что джава не так уж и плоха.

Ага, для IO-bound задач, если перенбрегать временем на старт :)

***** ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:38:21  
siberean

> случайно не SNP-чипы анализируются?

ага.

> Чем тогда bioconductor не устраивает?


у нас свои алгоритмы. Например, Half-IBD (Identity by descent) для нохождения участков полусовпадения, либо перегон сериез-матриц Бехара в другие форматы. bioconductor наверняка этого не умеет.

* ()
[#] Ответ на: комментарий от nu11 30.04.2011 11:35:36  
siberean

> а теперь 2 вопроса:

1) на выходе - как правило один файл. Всё равно надо мерджить. Как распараллеливать? Там не процессинг-баунд, а IO-баунд (переливать большие файлы из одного сосуда в другой, с какими-то преобразованиями).
2) можно сказать нисколько, я прежде всего думаю - как так прочитать файл - чтобы вывести нужный результат с наименьшим контекстом. Тот контекст обычно мал (если подходить чисто алгоритмически)

* ()
[#] Ответ на: комментарий от tailgunner 30.04.2011 18:48:10  
siberean

> Ага, для IO-bound задач, если перенбрегать временем на старт :)

Ну тогда буду писать на джаве, а не ANSI C.

Думаю, в генетике большинство задач будут IO-баунд, где объёмы данных в файле - гигабайты. У человека 2 миллиона снипов (если считать только то что сейчас считают, в будущем будет больше). И файлы могут быть на много-много строк, например для большой выборки или целой популяции. Если зафигачить в базу - там будет всё намного хуже.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:49:14  
siberean

Собираюсь также перегонять HAPMAP файлы (начал было но не закончил)

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:56:09  
siberean

> 1) на выходе - как правило один файл.

поправлюсь: конечно же не везде. Вот в преобразовании PED в формат RAW - на выходе получается куча файлов, каждый из которых - по миллиону снипов. Размер исходного - не определён и, думаю, может быть очень-очень большим.
Т.е. именно тот один фильтр-преобразователь можно было бы распараллелить. Но хочу ли я нагораживать pthreads только из-за одного фильтра - не уверен.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 19:02:43  
siberean

> Если зафигачить в базу - там будет всё намного хуже.

Правда сейчас идея пришла загрузить не в RDB, а в берклиDB (с ней я когда-то работал), без синхронизации, или в люцину, и работать с ней.
Будет время - попробую и люциновский вариант. Только для тех задач, где нужен очень большой контекст (т.е. есть правила-зависимости между строками) и надо много раз проходить.
Кстати, я иногда читаю один файл 22 раза (для каждой хромосомы), выбирая подмножество - чтобы не грузить гигабайт в память (это когда нужен мэп-хэш, и этот мэп большой). Ну не люблю я память рашодовать, насмотрелся как люди по 4 гигабайтов захавывают и им этого мало. Поэтому иду "снизу". По-крайней мере прочитав один файл много раз - не возникнет катастрофических проблем у юзера, с нехваткой памяти, краша. Ну, пусть будет немного более IO-баунд.

* ()
[#]  
pevzi

> портил

Как точно сказано (:

**** ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:45:48  
pevzi

> ЕМНИП там жита нет

Эм, а из-за чего ты думаешь там повышение производительности идет?

**** ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:37:30  
segfault

> ну я пробовал алгоритм Бернштейна, sdbm, алгоритм беркли ДБ используя свои простые структуры.

Так бы и сразу: это называется хеш-таблицы. Судя из ссылки на жж, сравнивалась современная реализация на яве и древний сишный СТЛ. Надо было хотя бы буст противопоставить...

> И пробовал B+tree ("красно-чёрные деревья", в терминах Кнута?) джавовский, получилось быстрее.

Предлагаю эту явовую реализацию запостить сюда: http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytrees&lang=all . Может, она что-то и поменяет в этом рейтинге. А пока, первое, что приходит в голову - это кривость реализации в случае Си.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 18:10:46  

> Свинг несравнимо богаче тикля.

ага, а gtk богаче с++

*** ()
[#] Ответ на: комментарий от pevzi 30.04.2011 19:31:53  
siberean

>> портил

> Как точно сказано (:


а для пользы дела, что-то конкретное сказать нечего? (кроме того что уже сказали)
Вон ахо я благодарен - за то что он меня ткнул в буфер и числа (В след.раз использую буферизированный read). Читать по чару всё равно надо (но уже из буфера), так как там совершенно не ясна длина рекордов (это же не старые-добрые fixed-length форматы, а delimited).

Есть конкретные предложения?

* ()
[#] Ответ на: комментарий от segfault 30.04.2011 19:56:48  
siberean

> Надо было хотя бы буст противопоставить...

Я буст не знал, каюсь. Был один большой проект на плюсах, до сих пор плююсь, ниасилил темплекты до конца и ломало классы прописывать. Да скецификацию, в отличие от тоненького K&R, нужно штудировать годами и иметь минимум десятилетие опыта, имхо, чтобы нормально на плюсах писать.

> Предлагаю эту явовую реализацию запостить сюда: http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytrees&lang=all . Может, она что-то и поменяет в этом рейтинге. А пока, первое, что приходит в голову - это кривость реализации в случае Си.


явовую реализацию чего? Конвертера кастомного, никому ненужного (кроме ресёрчеров) файла - в другой никому (из широкой публики) ненужный формат? Не засмеют? Потом надо большие файлы (гигабайтовые) готовить, искуственные, из ненастоящего генотипа, анонимный. Влом (это несколько часов скриптов). А оно мне надо?

* ()
[#] Ответ на: комментарий от elipse 30.04.2011 19:58:43  
siberean

>> Свинг несравнимо богаче тикля.

> ага, а gtk богаче с++


не понял коментария, если честно. Разверните, если можно, для тугодума.

* ()
[#] Ответ на: комментарий от segfault 30.04.2011 19:56:48  
siberean

> А пока, первое, что приходит в голову - это кривость реализации в случае Си.

Там же ничего нет, посмотрите сами.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 20:13:43  
segfault

> явовую реализацию чего? Конвертера кастомного, никому ненужного

Нет, работы с деревьями. Или это тоже что-то стандартное?

* ()
[#] Ответ на: комментарий от segfault 30.04.2011 20:27:51  
siberean

ааа, понятно.
ок, подумаю (для этого надо будет сделать интересные синтетические тесты)

* ()
[#] Ответ на: комментарий от elipse 30.04.2011 20:32:50  
siberean

> tcl (тикль) это язык, а tk - это gui.

когда я сказал "тикль" - я имел в виду конечно же ГУИ, tk (я думал, что тиклем в рунете зовут именно его, и только сейчас идентифицировал что
tcl (ти си эль) это может быть прочитано как ти-к-л (хотя тк было бы ближе по звучанию).

Я не делал сложных Гуёвин на нём, только кнопки, выбор файлов, выбор выводов и подобное. Это одна простыня скриптов, но для некоторых юзеров - это по-любому лучше чем коммандная строка.

Спасибо за скриншоты, буду иметь в виду.

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 20:58:29  
segfault

> ок, подумаю (для этого надо будет сделать интересные синтетические тесты)

В принципе, я бы хотел поучаствовать - например, предоставить сишный вариант реализации.

* ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:45:48  
sergej

Ты привел неудачный пример. Ядро изначально затачивалось на расширения gcc, но кто-то неск лет назад все таки собирал его каким-то другим компилятором.

Вобщем не будем флудить, моя мысль такова: если ява может работать с определенной скоростью, значит и на си можно написать не хуже. Цена этого "не хуже" конечно сильно зависит от конкретного проекта.

***** ()
[#] Ответ на: комментарий от DNA_Seq 30.04.2011 18:45:48  
annulen

>Попробуй собрать ведро компилятором отличным от gcc

Непортируемый код, не соответствующий стандарту, можно написать на любом языке. Между тем, ядро сейчас компилируется и clang, и icc

** ()
[#] Ответ на: комментарий от segfault 30.04.2011 21:11:04  
siberean

> В принципе, я бы хотел поучаствовать - например, предоставить сишный вариант реализации.

дык сделайте, и скажите - если я смогу быть чем-то полезным.

* ()
[#] Ответ на: комментарий от segfault 30.04.2011 21:11:04  
siberean

или хотите развивать сишный вариант аналога aisconvert (всего тулкита или отдельных тулзов? Там HIR search самый сложный. ped2raw - самый лёгкий, гомозиготность - в середине) - милости просим.
Я дал линки на проект выше. Ещё была давно новость: http://www.linux.org.ru/forum/talks/4895524.

Или лучше - делать такие проекты - которые ещё не реализованы ни на одном из языков, а люди ждут, и скажут спасибо.
Вот, регистрируйтесь на молгене и там есть какие-то спеки и примеры, типа:
http://forum.molgen.org/index.php/topic,2491.new/topicseen.html
(Бехаровские сериез-матрикс файлы или перегнать хапмапы во что-то совместимое с PLINK etc)

* ()
[#] Ответ на: комментарий от siberean 30.04.2011 22:44:43  
segfault

> дык сделайте, и скажите - если я смогу быть чем-то полезным.

Вы меня неправильно поняли - я имел в виду спор относительно быстродействия. Т.е. написать небольшой кусок кода на си, реализующий эти самые красно-чёрные деревья. Для участия даже в небольшом опен-сорс проекте у меня сейчас просто времени нет.

* ()
[#] Ответ на: комментарий от segfault 30.04.2011 23:36:21  
siberean

ну тогда хотя бы их напишите, сравните с хэшем по алгоритму Беркли DB, с C++овским ХэшМапом и джавовским ХэшМапом. С интересом почитаем результаты инсерта в и доступа к какому-нибудь много-миллионному массиву.

* ()
[#]  

с выходом из анабиоза, товарисч!

*** ()
[#] Ответ на: комментарий от siberean 30.04.2011 21:04:16  
proud_anon

>когда я сказал "тикль" - я имел в виду конечно же ГУИ, tk (я думал, что тиклем в рунете зовут именно его, и только сейчас идентифицировал что
tcl (ти си эль) это может быть прочитано как ти-к-л (хотя тк было бы ближе по звучанию).

Так ведь не только в Рунете, его как раз в англоязычных Интернетах так в первую очередь называют. Дискуссия тут: http://wiki.tcl.tk/11902

*** ()
[#] Ответ на: комментарий от proud_anon 01.05.2011 0:34:47  
siberean

ну не слышал я от сотрудников тикль, каюсь. Только ти-си-эль. Потому что си это си, а не кэ, когда отдельным звуком.

* ()