1. Java / Говнокод #26808

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    import java.util.concurrent.TimeUnit;
    import java.util.regex.Pattern;
    import static java.lang.System.*;
    import static java.util.concurrent.TimeUnit.NANOSECONDS;
    
    public class Rep implements CharSequence
    {
        String str = null;
        int    len;
        char  base;
    
        public Rep(char x, int count)
        {
            this.len  = count;
            this.base = x;
        }
    
        @Override
        public int length()
        {
            return len;
        }
    
        @Override
        public char charAt(int index)
        {
            return base;
        }
    
        @Override
        public CharSequence subSequence(int beginIndex, int endIndex)
        {
            if (beginIndex < 0) {
                throw new StringIndexOutOfBoundsException(beginIndex);
            }
            if (endIndex > this.len) {
                throw new StringIndexOutOfBoundsException(endIndex);
            }
            int subLen = endIndex - beginIndex;
            if (subLen < 0) {
                throw new StringIndexOutOfBoundsException(subLen);
            }
            return ((beginIndex == 0) && (endIndex == this.len)) ? this
                    : new Rep(this.base, subLen);
        }
    
        @Override
        public String toString()
        {
            return null!=str ?  str : (this.str  = new String(new char[]{base}).repeat(len));
        }
    
        public static void main(String... args)
        {
            long ns = 0L;
            Pattern lazy   = Pattern.compile("^(11+?)\\1+$");
            Pattern greedy = Pattern.compile("^(11+?)\\1+$");
            ns=nanoTime();  lazy  .matcher(new Rep('1',100160079)).matches(); out.println( NANOSECONDS.toMillis(nanoTime()-ns));
            ns=nanoTime();  greedy.matcher(new Rep('1',100160079)).matches();out.println( NANOSECONDS.toMillis(nanoTime()-ns));
            ns=nanoTime();  greedy.matcher(new Rep('1',1165139)).matches();out.println( NANOSECONDS.toMillis(nanoTime()-ns));
    
            ns=nanoTime(); "1".repeat( 100160079 ).matches("^(11+?)\\1+$") ; out.println("Lazy String:"+ NANOSECONDS.toMillis(nanoTime()-ns));
            ns=nanoTime(); "1".repeat( 100160079 ).matches("^(11+)\\1+$") ; out.println("Greedy String:"+ NANOSECONDS.toMillis(nanoTime()-ns)); 
        }
    
    }

    Так как в «Йажа» регулярки работают не на строках, а на интерфейсе CharSequence https://docs.oracle.com/javase/8/docs/api/index.html?java/lang/CharSequence.html

    Решил что можно сделать тупую реализацию CharSequence для строк из повторяющегося символа.

    https://ideone.com/8eYFU7

    Запостил: 3.14159265, 16 Июля 2020

    Комментарии (81) RSS

    • Ideone результаты
      Lazy Rep:210
      Greedy Rep:272
      Lazy String:912
      Greedy String: Time limit [5s] exceeded 137364KB
      
      без "1".repeat( 100160079 )
      
      Lazy Rep:196
      Greedy Rep:200
      Success	#stdin #stdout 0.49s 36600KB
      Ответить
    • > "1".repeat( 100160079 )

      ну кто ж так бенчит? создание тестовых данных за пределы измеряемого времени-то вынеси
      Ответить
      • А тогда надо было и скриптушню иначе мерить.
        Ответить
        • Кстати подозреваю что в скриптушне malloc/memset шло не в user, а в sys. Который занимал 25-30%.
          Ответить
      • Так это не создание тестовых данных, а часть алгоритма.

        Впрочем заполнение строки питушнёй настолько несущественно, что разница там в пределах погрешности.
        Стало даже чуть хуже
        Lazy String : 1092

        https://ideone.com/M6ZXhR
        Ответить
        • какого алгоритма? ты регэкспы меряешь или что? аллокацию? так у тебя только один пример аллоцирует. а -XX:AlwaysPreTouch выставил? а хип сколько вообще сначала был? а гц смотрел? а не компилит ли что-то джит между вызовами смотрел? а сколько оно работает интерпретатором смотрел? а в с1? а в с2? а инлайн принудительный делал? а ассемблерный листинг смотрел?

          это и близко не бенчмарк, какая-то хуйня внутри происходит, ну да и ладно.
          Ответить
          • Это сравнение алгоритма проверки числа на простоту при помощи рагулярных выражений. Во всех сравниваемых языках он один и тот же.
            Ответить
            • ну да, давайте всякую хуйню типа аллокации не считать, она же во всех языках одинаковая, конечно
              Ответить
              • Ну а зачем её считать, если мы меряем производительность на реальной задаче?
                Ответить
                • ты там всё-таки определись, одинаковый рантайм или нет

                  мало того, что жажа уже при стартапе загружает кучу всего, так и внутри вызова может наткнуться на какой-то незагруженный класс и пойти читать с диска
                  Ответить
                  • Ещё раз повторюсь: какая разница? Никого не волнует, какой там рантайм и какие оно классы грузит. Есть реальная задача, мы меряем, насколько быстро её решает тот или иной язык. Всё.
                    Ответить
                    • мне это напоминает видео, где чувак объяснял, что он предпочел мак винде, потому что там пнг в буфер обмена копируются с альфа-каналом

                      да, реальная задача
                      Ответить
                      • Ну а чо, проверка числа на простоту — такая уж нереальная задача?

                        И да, копирование картинок в буфер обмена в винде — это ёбанное днище.
                        Ответить
                        • В «ДОСе» нет никакого буфера обмена. Именно поэтому я за «ДОС».
                          Ответить
                        • > копирование
                          Лоооооол
                          Виндобляди соснули
                          Ответить
                        • Проверка чисел на простоту с помощью абьюза движка регэкспов - точно не реальная задача для языка.
                          Ответить
                  • >мало того, что жажа уже при стартапе загружает кучу всего, так и внутри вызова может наткнуться на какой-то незагруженный класс

                    У себя я бенчил из jshella.
                    Со стартованной йажей и загруженными классами.
                    Ответить
                    • А надо бенчить из graal vm AOT compilation.
                      Ответить
                      • >надо бенчить из graal vm AOT compilation.

                        Я не хочу пирдолиться чтобы создать тепличные условия сраной Йаже, которой в отличие от быстрой однострочной скриптухи (!) нужен ещё какой-то пирдолинг с «питухвм», и КОКОКОмпилятором.

                        И всё ради того чтобы выиграть жалкие 3 секунды. Чтобы Йажа соснула не за 1410 секунд, а всего за 1407.

                        Надо не питухвмы городить, а делать оптимизированный зожимающий repeat, который не засирает мегабайты памяти.
                        Ответить
                        • > которой в отличие от быстрой однострочной скриптухи (!) нужен ещё какой-то пирдолинг с «питухвм», и КОКОКОмпилятором.
                          Подтверждаю. Скриптуху вообще time'ом измеряли, со всеми накладными расходами на запуск процесса и безо всяких прогревов.
                          Ответить
    • Вообще я пытался починить огромное пеналти «Йажа» на простых числах.

      long ns=nanoTime(); lazy.matcher("1".repeat( 1165139 )).matches(); out.println("Lazy String : "+ NANOSECONDS.toMillis(nanoTime()-ns));
      Lazy String : 1416.544 sec
      
      > long ns=nanoTime();  lazy  .matcher(new Rep('1', 1165139 )).matches(); out.println("Lazy Rep:"+ NANOSECONDS.toMillis(nanoTime()-ns));
      Lazy Rep: 92.476 sec


      А она всё-равно пёрлу сливает

      time perl -wle 'print "Prime" if (1 x shift) !~ /^(11+?)\1+$/' 1165139
      Complex regular subexpression recursion limit (32766) exceeded at -e line 1.
      Prime
      
      real	0m28.459s
      user	0m28.454s
      sys	0m0.004s
      Ответить
      • > сливает

        > Complex regular subexpression recursion limit (32766) exceeded at -e line 1.

        ты exit code-то хоть проверял?
        Ответить
        • В соседнем треде читай, всё в порядке там с exit code (и результатами).
          Ответить
          • да плевать, движок же прямо говорит, что он регулярку до конца не процессит
            Ответить
            • Он такого не говорит.
              Результаты он выдаёт полностью корректные, так что действительно плевать.
              Ответить
              • а это что?

                > Complex regular subexpression recursion limit (32766) exceeded at -e line 1.
                Ответить
                • "But the Complex regular subexpression recursion limit makes perl just say "oh well, I had enough - I'll just pretend it doesn't match". That's wrong. It may even be exploitable."
                  Ответить
                • См. ветку https://govnokod.ru/26800#comment559641 (да и вообще весь тред).
                  Ответить
                  • смотрю, вижу

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

                    ну то есть опять приходим к тому, что жажа выолняет одно, а пердл другое
                    Ответить
                    • Для чисел меньше 1073938441 «Перл» всегда будет выдавать корректный результат. С тем же успехом можно обвинить ЙАЖУ в том, что она не сможет корректно обработать числа длиннее 2**31.

                      > ну то есть опять приходим к тому, что жажа выолняет одно, а пердл другое
                      Все языки выполняют разное, потому что у них у всех разные реализации движка рагулярных выражений.
                      Ответить
                    • А зачем тогда вообще мерить, откуда бы разнице взяться, если бы они реально ОДНО И ТО ЖЕ делали?
                      Ответить
                      • в жаже строчки только в двойных кавычках - в «PHP», как мы знаем, эту проблему перформанса можно обойти
                        Ответить
                        • Именно поэтому я за «PHP».
                          Ответить
                          • А я за «Python»: там есть одинарные, двойные, тройные и даже шестерные кавычки.
                            Ответить
                          • L.warn(f'Invalid HMAC "{sign[:128]}{"..." if len(sign) > 128 else ""}" from {user}/{ip}')

                            Разве не красиво? И это я только два вида кавычек использовал!
                            Ответить
                            • На руби пох0же
                              l.warn "Invalid HMAC #{sign[0..2].to_s + '...' if sign.length > 2} from #{user}/#{ip}"
                              Ответить
                              • > + '...' if sign.length > 2
                                Красиво. Всё таки «Руби» — очень сладкий язык.
                                Ответить
                        • Так вот почему ЙАЖА так тормозит! Тайна века раскрыта!
                          Ответить
                          • На самом деле я подумал и понял что соснули все. Скопом.

                            В каждом языке сделали специальный оператор/метод для повтора строки.

                            Есть перл, 1 x 75120045
                            Есть руби и питух "1" * 75120045
                            В йажа завезли "1".repeat( x ).

                            Но сделали анскильно.

                            В той же йажа строки немутабельные. То есть раз мы создали миллион "1" он таким навсегда и останется

                            Неужели действительно нельзя было сделать чтобы repeat возвращал простой CharSequence. Содержащий повторяемую строку и количество повторений.

                            И не плодить строки с гигабайтом повторяющихся символов?

                            Конкретно в этой задаче это дало ускорение 5-15 раз. И константу по памяти.
                            Ответить
                            • А зачем этот супер рипит? Чтобы быстро и экономно по памяти отдавать i-ый символ строки? Ну просто движок регэкспов же не станет с таким работать, эм ай райт? Ну и нахуя экономия, чьё время жизни в промежутке от иммутабельной инициализацией, где ничего с данными произойти не может, до ближайшего тустринг.

                              Или ты заставил регэкспы работать с каким нибудь потоком String и заимплементил интерфейс?
                              Ответить
                              • >у просто движок регэкспов же не станет с таким работать, эм ай райт?
                                Будет.

                                >Или ты заставил регэкспы работать с каким нибудь потоком String и заимплементил интерфейс?

                                Вообще-то пример кода в посте. https://govnokod.ru/26808
                                Ответить
                              • >чьё время жизни в промежутке от иммутабельной инициализацией где ничего с данными произойти не может, до ближайшего тустринг.

                                В примере из поста toString вообще не вызывается. На что указывает маленькое количество памяти в тестах. Движок регэксов откусывает из последовательности по символу.

                                Т.к. код не лазит постоянно в память, а берёт символы из ближайшего кеша алгоритм ускоряется в 5-15 раз.

                                Такое встречается довольно часто. Иногда нужно сгенерить последовательность символов для итерации.

                                CharSequence можно представить как ленивый список из Хацкеля. Он в теории мог быть даже бесконечным, если бы не int length().
                                Ответить
                                • Да, охуенно!
                                  Ответить
                                • Надо всё так хранить, у чего низкая сложность по Колмогорову.
                                  Ответить
                                  • https://codegolf.stackexchange.com/questions/69189/build-a-compiler-bomb
                                    Ответить
                                    • И даже в этом конкурсе Сишка опять всех элегантно слила.
                                      main[-1u]={1};
                                      Ответить
                                      • Не, там «Путух» всех слил.
                                        Python 3, 16 byte source, >32TB .pyc-file (if you have enough memory, disk space and patience)
                                        (1<<19**8,)*4**7
                                        Ответить
                                        • Длинная арифметика из коробки — это его киллер-фича.
                                          Ответить
                                          • Тут длинной орейфметики нет, тут просто злоупотребление путуховской свёрткой коньстант.
                                            Ответить
                                        • >(1<<19**8,)*4**7
                                          >main[-1u]={1};

                                          Сишка компактнее. И на мой вкус изящнее.

                                          Путушное решение скучное.
                                          А с main[] я вообще удивился что эта питушня компилится.
                                          Ответить
                                          • > Сишка компактнее.
                                            Плотность в гигабайтах на байт исходного кода всё равно выше.

                                            > И на мой вкус изящнее.
                                            А тут соглашусь, великолепный трюк.
                                            Ответить
                                            • >Плотность в гигабайтах на байт исходного кода всё равно выше.

                                              Какая разница сколько там воображаемых петабайт, если эта плотность недостижима на практике? Сишка практичнее.

                                              Компиляцию Питуха невозможно проверить на практике, т.к. нет столько ОЗУ.

                                              А когда столько ОЗУ и дискового пространства появится, то в Сишку просто завезут 128-битные типы и более широкую адресацию.

                                              -1lu переполнится в ещё большие числа.
                                              Ответить
                                          • main[42]={1};

                                            Выхлоп gcc -S a.c:
                                            .file	"a.c"
                                            	.text
                                            	.globl	_main
                                            	.data
                                            	.align 32
                                            _main:
                                            	.long	1
                                            	.space 164
                                            	.ident	"GCC: (Rev2, Built by MSYS2 project) 9.2.0"

                                            Выхлоп bcc32 -S a.c:
                                            .386p
                                            	ifdef ??version
                                            	if    ??version GT 500H
                                            	.mmx
                                            	endif
                                            	endif
                                            	model flat
                                            	ifndef	??version
                                            	?debug	macro
                                            	endm
                                            	endif
                                            	?debug	S "a.c"
                                            	?debug	T "a.c"
                                            _TEXT	segment dword public use32 'CODE'
                                            _TEXT	ends
                                            _DATA	segment dword public use32 'DATA'
                                            _DATA	ends
                                            _BSS	segment dword public use32 'BSS'
                                            _BSS	ends
                                            DGROUP	group	_BSS,_DATA
                                            _DATA	segment dword public use32 'DATA'
                                            	align	4
                                            _main	label	dword
                                            	dd	1
                                            	db	164	dup(?)
                                            _DATA	ends
                                            _TEXT	segment dword public use32 'CODE'
                                            _TEXT	ends
                                            	public	_main
                                            	?debug	D "a.c" 20722 39453
                                            	end

                                            Выхлоп wcc386 a.c; wdis -a a.obj:
                                            .387
                                            .386p
                                            		PUBLIC	_main
                                            DGROUP		GROUP	CONST,CONST2,_DATA
                                            _TEXT		SEGMENT	BYTE PUBLIC USE32 'CODE'
                                            _TEXT		ENDS
                                            CONST		SEGMENT	DWORD PUBLIC USE32 'DATA'
                                            CONST		ENDS
                                            CONST2		SEGMENT	DWORD PUBLIC USE32 'DATA'
                                            CONST2		ENDS
                                            _DATA		SEGMENT	DWORD PUBLIC USE32 'DATA'
                                            _main:
                                                DB	1, 0, 0, 0, 0, 0, 0, 0
                                                DB	013H DUP(0,0,0,0,0,0,0,0)
                                                DB	0, 0, 0, 0, 0, 0, 0, 0
                                            
                                            _DATA		ENDS
                                            		END

                                            «Цифровой Марс» выдаёт то же, что и «Watcom».

                                            «MSVC» генерирует аналогичную питушню, разве что вставляет комментарий:
                                            .asciiz	"   /DEFAULTLIB:\"LIBCMT\" /DEFAULTLIB:\"OLDNAMES\" "

                                            Интеловский компилятор ведёт себя аналогично «MSVC».

                                            Выхлоп lcc -S a.c:
                                            .file	"d:\workdir\c\hack\a.c"
                                            _$M0:
                                            	.file	"d:\workdir\c\hack\a.c"
                                            	.text
                                            	.data
                                            	.globl	_main
                                            	.align	2
                                            	.type	_main,object
                                            _main:
                                            	.long	1
                                            	.space	164

                                            Выхлоп clang -S a.c:
                                            .text
                                            	.def	 @feat.00;
                                            	.scl	3;
                                            	.type	0;
                                            	.endef
                                            	.globl	@feat.00
                                            @feat.00 = 1
                                            	.data
                                            	.globl	_main                   # @main
                                            	.p2align	2
                                            _main:
                                            	.long	1                       # 0x1
                                            	.long	0                       # 0x0
                                            И ещё 40 директив .long	0


                                            И даже «tcc» Фабриса Беллара генерирует такой же массив.
                                            Ответить
                                          • Оно работает даже с pituh[-1u]={1};

                                            В «K&R C» был «автовывод» типов: все необъявленные скаляры считались типа int, у всех необъявленных массивов тип элемента был int, у всех необъявленных функций тип результата был int.

                                            Поэтому pituh[-1u]={1}; эквивалентен int pituh[-1u]={1};

                                            Т. е. объявляем массив интов, в квадратных скобках размер, в фигурных — начальные значения некоторого среза массива, начиная с нулевого элемента (всё, что явно не инициализировали в фигурных скобках, инициализируется нулём).

                                            В сишке нельзя инициализировать массив частично: можно или вообще не инициализировать (тогда он не попадёт в экзешник, а будет создаваться при загрузке программы), либо инициализировать полностью (компилятор за нас запишет нули в элементы, которые мы пропустили).

                                            main — это не конструкция языка, это всего лишь известный символ в стандартной библиотеке. Успешной линковки и отладки, когда код из CRT вызовет _main, а в нём массив, начинающийся с единички, вместо вменяемого кода.
                                            Ответить
                                          • Реальный пример успешно завершающейся программы:
                                            main[1]={0xc3};


                                            main объявлен как массив из одного элемента со значением 0xc3 (что совпадает с опкодом RET у x86). Поскольку у x86 маленький индеец, 0xc3 будет самым первым байтом, а нули будут потом.

                                            Может не сработать из-за DEP, если поддерживается атрибут NX.
                                            Ответить
                                            • У меня
                                              ./a.out 
                                              Segmentation fault
                                              ➤ 139

                                              В целом, да. Можно написать в машинных кодах какие-то вычисления, переместить в rax и вывести их в консоль через код разврата.
                                              // mov    eax,0x2a; b8 2a 00 00 00
                                              // ret      ; 0xc3
                                              main[]={0x00002ab8,0x00c300};
                                              Ответить
                                              • В «gcc» и в «clang» нужно писать так:
                                                main[1]__attribute__((section(".text")))={0xc3};

                                                В «MSVC», «Borland C», «Watcom C» нужно писать так:
                                                #pragma codeseg(".text")
                                                __declspec(allocate(".text"))main[1]={0xc3};

                                                Первая строка не нужна, потому что секция ".text" уже имеется. Эта строка нужна, чтобы заткнуть компилятор.
                                                Ответить
                                                • А зойчем [1]?
                                                  Ответить
                                                  • Действительно, можно же [], чтобы компилятор сам посчитал размер.
                                                    Ответить
                                                    • А вот такой код работает!
                                                      Умножает argc на 3.

                                                      main[]__attribute__((section(".text")))={0xc37f048d};
                                                       lea    eax,[rdi+rdi*2] ; 8d 04 7f
                                                       ret                         ;c3
                                                      Ответить
                                                • Проверил. Код ответа 40

                                                  main[]__attribute__((section(".text")))={0xc3};
                                                   ^~~~
                                                  bomb.c:1:1: warning: type defaults to ‘int’ in declaration of ‘main’ [-Wimplicit-int]
                                                  /tmp/cc6Zi9tY.s: Assembler messages:
                                                  /tmp/cc6Zi9tY.s:4: Warning: ignoring changed section attributes for .text
                                                  ➤ 40


                                                  А вообще реальные Цари не пишут main, а начинают программу переопределяя _start.
                                                  Ответить
                                                • Похоже ret недостаточно, ибо в rax мусор.

                                                  Его нужно почистить, чтобы получить нулевой код разврата.

                                                  Но хорошо, что у Штеуд в 4 байта вмещается 2 инструкции благодаря variable length схеме.
                                                  main[]__attribute__((section(".text")))={0xc3c031};
                                                  xor    eax,eax; 31 с0

                                                  И наконец-то мы получаем Success с нулём.
                                                  https://ideone.com/CCTOQT
                                                  Ответить
                                      • И тут мы приходим к тому, о чём я уже говорил.
                                        Ответить
        • > ты exit code-то хоть проверял?

          Не нужно хамить.

          У приличных людей он в промпте автоматом выводится.

          Кстати не понимаю почему это нигде не настроено по дефолту и в каждом дистре (даже где есть готовые презеты промпта) не настроено отображение кода и приходится его руками вписывать.

          Мне код возврата в 90% гораздо важнее знать, чем текущую директорию, текущее время, юзера и прочую питушню.
          Ответить
          • > ты exit code-то хоть проверял?
            какой сёмизм:)

            Я запускаю код из IDE, она всегда рисуует exit code
            Ответить
      • > пёрлу

        Сишке же. Жаба честно регулярки считает, а пёрл всё сишке скармливает.
        Ответить
        • >Сишке же

          ЧЯДНТ?

          https://govnokod.ru/26800#comment559728

          https://ideone.com/2MelzP
          Ответить
    • Performance в джаве без разогрева он всегда разный. JMH вот этот вот все
      Ответить

    Добавить комментарий