Пользователь
Прошел ровно год с момента прошлой публикации и я подумал что первое апреля — отличный день для ежегодного дайджеста по моим трем безумным компьютерным проектам. В тот раз проект существовал только на бумаге, теперь же — определенно стал реальностью.
Подкатом звенящие релейные блоки, самые быстрые в мире вычисления на реле(но это не точно), монтаж накруткой, вакуумные индикаторы и моргающие светодиодики.
Впервые про TECO я прочитал в пародийной статье Real Programmers Don't Use Pascal, написанной незадолго до моего рождения. Там было написано, что настоящие программисты не используют новомодные редакторы EMACS и VI:
Нет, Настоящий Программист хочет редактор вида «Просил? Так получай!» — сложный, загадочный, мощный, не прощающий ошибок, опасный. TECO, если быть точным.
ОригиналNo, the Real Programmer wants a `you asked for it, you got it' text editor — complicated, cryptic, powerful, unforgiving, dangerous. TECO, to be precise.
Это меня заинтриговало. Что за зверь такой, можно ли его пощупать? Википедия рассказала, что TECO — это Text Editor & COrrector, создан он в 1962-м году в DEC и использовался на компьютерах семейства PDP, а позже на системах OpenVMS. Оказалось, что существует порт на Си, который поддерживается энтузиастами в актуальном состоянии и собирается под современными операционными системами. Вот я и решил почувствовать себя настоящим программистом хотя бы немножко.
Камень бросают вертикально, без начальной скорости с высоты h = 100 м. Пренебрегая сопротивлением воздуха, определить закон движения камня, как функцию высоты камня над поверхностью Земли от времени. Ускорение свободного падения принять равным 10 м/с2Простая задачка? Да элементарная, имеющее аналитическое решение, которое легко напишет мало-мальски грамотный школьник. Но эта простая задача послужит нам весьма показательным примером
Содержание:
Последовательность Фибоначчи O (n)
Решение за O(n ^ 2)
Бинарный поиск O(log n)
Решение за O(n * log n)
"Найти длину самой большой возрастающей подпоследовательности в массиве."
Вообще, это частный случай задачи нахождения общих элементов 2-х последовательностей, где второй последовательностью является та же самая последовательность, только отсортированная.
Есть последовательность:
5, 10, 6, 12, 3, 24, 7, 8
Вот примеры подпоследовательностей:
10, 3, 8
5, 6, 3
А вот примеры возрастающих подпоследовательностей:
5, 6, 7, 8
3, 7, 8
А вот примеры возрастающих подпоследовательностей наибольшей длины:
5, 6, 12, 24
5, 6, 7, 8
Вдохновение на написание данной статьи было получено после прочтения похожей публикации для архитектуры x86 [1].
Данный материал поможет тем, кто хочет понять, как устроены программы изнутри, что происходит до входа в main и для чего всё это делается. Также я покажу как можно использовать некоторые особенности библиотеки glibc. И в конце, как и в оригинальной статье [1] будет визуально представлен пройденный путь. В большинстве своём статья представляет собой разбор библиотеки glibc.
Итак, начнём наш поход. Будем использовать Linux x86-64, а в качестве инструмента отладки — lldb. Также иногда будем дизассемблировать программу при помощи objdump.
Исходным текстом будет обычный Hello, world (hello.cpp):
#include <iostream>
int main()
{
std::cout << "Hello, world!" << std::endl;
}
(с) xkcd
Это продолжение цикла статей о том, как я занимался оптимизацией и получил самый быстрый ресайз на современных x86 процессорах. В каждой статье я рассказываю часть истории, и надеюсь подтолкнуть еще кого-то заняться оптимизацией своего или чужого кода. В предыдущих сериях:
→ Часть 0
→ Часть 1, общие оптимизации
В прошлый раз мы получили ускорение в среднем в 2,5 раза без изменения подхода. В этот раз я покажу, как применять SIMD-подход и получить ускорение еще в 3,5 раза. Конечно, применение SIMD для обработки графики не является ноу-хау, можно даже сказать, что SIMD был придуман для этого. Но на практике очень мало разработчиков используют его даже в задачах обработки изображений. Например, довольно известные и распространенные библиотеки ImageMagick и LibGD написаны без использования SIMD. Отчасти так происходит потому, что SIMD-подход объективно сложнее и не кроссплатформенный, а отчасти потому, что по нему мало информации. Довольно просто найти азы, но мало детальных материалов и разбора реальных задач. От этого на Stack Overflow очень много вопросов буквально о каждой мелочи: как загрузить данные, как распаковать, запаковать. Видно, что всем приходится набивать шишки самостоятельно.
Многие из нас в школе или университете посещали уроки черчения, но не многим из нас это нравилось. Часами возиться с линейкой, циркулем и плохо заточенным карандашом, пытаясь ровно и без помарок выводить размерные линии, бесконечные штриховки и странные формы, мало кому могло показаться интересным. Тем более, что к тому времени уже существовали компьютерные программы, способные автоматизировать это скучное, бессмысленное и беспощадное занятие. А настоящий прорыв в области проектирования деталей и подготовки конструкторской документации произошел в 1989 вместе с дебютом параметрического моделирования в Системе Автоматизированного Проектирования (САПР) Pro/Engineer.
Это — вводная статья к циклу статей "Параметрическое моделирование". Из этого цикла вы узнаете о внутреннем устройстве настоящего решателя геометрических ограничений, проблемах и их решениях на примере open-source САПР "SolveSpace". Кому не чужд мир трехмерного моделирования, добро пожаловать под кат!
Модель ударно-спускового механизма РПГ-7, созданная в САПР SolveSpace
