Просторовий індекс для PostgreSQL на основі Z-order (vs R-tree), продовження


минулий раз ми прийшли до висновку, що для ефективної роботи просторового індексу на основі Z-order необхідно зробити 2 речі:
  • ефективний алгоритм отримання подинтервалов
  • низькорівневу роботу з B-деревом
Ось саме цим ми і займемося під катом.
Читати далі →

Персона. Командир Нортон

image

Пітер Нортон відомий більшості користувачів персональних комп'ютерів. Правда, не всі про це замислюються, не всі уявляють, наскільки великі його заслуги. За плечима Пітера роки роботи над такими продуктами, як Norton Commander, Norton Utilities, Norton Disk Doctor. Він також є автором таких популярних книг, як «Всередині IBM PC», «Всередині OS/2» і «Довідник програміста».

Нортон створив новий напрямок розробки ПО. Він був новатором і з точки зору ринку, і в технічному плані. Однак Пітер Нортон працював не заради грошей і слави. Принаймні, сам він у це вірить.
Читати далі →

Як PVS-Studio шукає помилки: методики і технології

Що всередині у PVS-StudioPVS-Studio — статичний аналізатор вихідного коду для пошуку помилок і вразливостей в програмах на мові C, C++ і C#. У цій статті я хочу дати огляд технологій, які ми використовуємо в аналізаторі PVS-Studio для виявлення помилок в коді програм. Крім загальної теоретичної інформації я буду на практичних прикладах показувати, як та чи інша технологія дозволяє виявляти помилки.

Введення
Приводом для написання статті стало мій виступ з доповіддю на відкритій конференції ІСП РАН 2016 (ISPRAS OPEN 2016), що проходила в перших числах грудня в Головній будівлі Російської академії наук. Тема доповіді: «Принципи роботи статичного аналізатора коду PVS-Studio» (презентація у форматі pptx).

На жаль, час виступу було сильно обмежено, тому мені довелося підготувати досить коротку презентацію і не розповісти в доповіді багато чого з того, що хотілося. Тому я вирішив написати цю статтю, де більш детально розповім про те, які підходи і алгоритми ми використовуємо при розробці проекту PVS-Studio.

Читати далі →

Nuklear — ідеальний GUI для мікро-проектів?

Nuklear — це бібліотека для створення immediate mode користувальницьких інтерфейсів. Бібліотека не має ніяких залежностей (тільки C89! тільки хардкор!), але і не вміє створювати вікна операційної системи або виконувати реальний рендеринг. Nuklear — вбудована бібліотека, яка надає зручні інтерфейси для відтворення засобами реалізованого програми. Є приклади на WinAPI, X11, SDL, Allegro, GLFW, OpenGL, DirectX. Батьком концепції була бібліотека ImGUI.
Чим прекрасна саме Nuklear? Вона має невеликий розмір (близько 15 тисяч рядків коду), повністю міститься в одному заголовочном файлі, створювалася з упором на портативність і простоту використання. Ліцензія Public Domain.
Читати далі →

Про Z-оrder і R-дерево

image
Індекс на основі Z-order кривої в порівнянні з R-деревом має масу переваг, він:
  • реалізований як звичайне B-дерево, а ми знаємо що
  • сторінки B-дерева мають кращу заповнюваність, крім того,
  • Z-ключі самі по собі більш компактні
  • B-дерево має природний порядок обходу, на відміну від R-дерева
  • B-дерево швидше будується
  • B-дерево краще збалансовано
  • B-дерево зрозуміліше, не залежить від евристики поділу/злиття сторінок
  • B-дерево не деградує при постійних змінах
  • ...
Втім, у індексів на основі Z-order є і недолік — порівняно низька продуктивність :). Під катом ми спробуємо розібратися з чим пов'язаний цей недолік і чи можна щось з цим зробити.

Читати далі →

Створення і тестування Firewall в Linux, Частина 2.2. Таблиці Firewall. Доступ до TCP\IP структурам

Як 10 років тому починався проект PVS-Studio

Єдиноріг

Десять років тому ми створили просту утиліту під назвою Viva64, призначену для виявлення деяких проблем в 64-бітному коді. Так було закладено початок статичного аналізатора коду PVS-Studio. Хоча з того моменту пройшло 10 років, що більш-менш у нас, як у компанії, стало виходити лише кілька років тому. Ця стаття — не історія успіху, так як ми вважаємо, що все найцікавіше тільки починається. Однак, 10 років — це привід підбити проміжні підсумки і розповісти нашим читачам як все починалося, які нас чекали помилки, і що на даний момент у нас вийшло. Місцями я, можливо, буду не зовсім хронологічно точний при описі подій. Моя пам'ять не ідеальна, а 10 років — це тривалий проміжок часу. Бажаю всім приємного читання.

Читати далі →

Складна проблема комьютерных наук

… це, звичайно ж, іменування сутностей. І я говорю не тільки про імена змінних або нових технологій, немає. Ми не можемо домовитися навіть про самих базових термінах.

Тисяча діалектів
Чи знаєте ви, що специфікація мови програмування часто згадує термін «об'єкт»? Ні, це не об'єкт в тому розумінні, як він описується в ООП — об'єкт Із визначається як «блок даних в середовищі виконання, вміст якого може представляти деяке значення». В цьому розумінні об'єкта має сенс говорити про, наприклад, «об'єкт типу char».

Термін «метод» досить поширений, але ви можете зустріти програмістів, які будуть говорити виключно «функція-член класу». Мова програмування Java, тому, чи має, то не має функцій, в залежності від того, кого ви про це запитаєте. Терміни «процедура» і «підпрограма» іноді використовується як аналог «функції», але в деяких мовах програмування (наприклад, Pascal) процедура це зовсім не те ж саме, що функція.

Навіть у межах однієї мови програмування ми, буває, плутаємося.

Читати далі →

Створюючи хтонічних чудовиськ, документируй

ioninja
Під цим висловом, узятим з чудової картинки-мема невідомого (принаймні, мені) автора, поставить свій підпис кожна людина, що має хоча б віддалене відношення до програмування. все питання, як? Як саме документувати?
Нижележащий текст переслідує кілька цілей:
  1. По-перше, дати короткий огляд (читай — трохи погундеть на тему) незадовільного стану інструментарію, що застосовується до хтонічним чудовиськам світу C/C++;
  2. По-друге, запропонувати своє альтернативне рішення (безкоштовно без СМС та реєстрації — проект некомерційний і викладений на GitHub під MIT-ліцензією);
  3. -третє, закликати співтовариство поспілкуватися на тему і зібрати ідеї;
  4. В-четвертих, запросити долучитися до розробки проекту на GitHub.
Відразу обмовлюся, що хоча проект створювався в першу чергу як альтернатива, а точніше, доповнення Doxygen для сишных і плюсових API, архітектурно він в рівній мірі придатний і для інших мов. Це дозволяє створювати портали документації різнопланових бібліотек — самі бібліотеки можуть бути написані на різних мовах, а в документації єдність стилю у зовнішньому вигляді та поведінці.


Читати далі →