https://wiki.cs.hse.ru/api.php?action=feedcontributions&feedformat=atom&user=Rkovalev 2026-09-21T12:21:11Z Вклад MediaWiki 1.43.9 https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17993 2015-12-15T14:39:26Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> <br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> <br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17992 2015-12-15T14:39:12Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17991 2015-12-15T14:38:43Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17990 2015-12-15T14:38:17Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство различных энтропийных алгоритмов сжатия, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17989 2015-12-15T14:37:46Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17988 2015-12-15T14:36:47Z

<p>Rkovalev: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> Для измерения производительности мы будем применять perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17987 2015-12-15T14:35:33Z

<p>Rkovalev: /* Что это за проект? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные алгоритмы сжатия и научитесь создавать свои, а также научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> Для измерения производительности мы будем применять perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17986 2015-12-15T14:35:16Z

<p>Rkovalev: /* Что это за проект? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [[https://github.com/gtoubassi/femtozip femtozip]] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные алгоритмы сжатия и научитесь создавать свои, а также научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> Для измерения производительности мы будем применять perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17985 2015-12-15T14:34:04Z

<p>Rkovalev: /* Что это за проект? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать такой алгоритм сжатия и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [[https://github.com/gtoubassi/femtozip femtozip]] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные алгоритмы сжатия и научитесь создавать свои, а также научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> Для измерения производительности мы будем применять perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%BC%D0%B0%D0%BB%D1%8B%D1%85_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B5%D0%B9_%D0%B4%D0%BB%D1%8F_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17984 2015-12-15T14:33:37Z

<p>Rkovalev: Новая страница, с помощью формы Новый_проект</p> <hr /> <div>{{Карточка_проекта<br /> |name=Компактное сжатие малых записей для быстрого доступа<br /> |mentor=Руслан Ковалёв<br /> |mentor_login={{URLENCODE:Rkovalev|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (например, мы можем представить себе таблицу в высоко нагруженной базе данных). <br /> <br /> В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать такой алгоритм сжатия и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [[https://github.com/gtoubassi/femtozip femtozip]] на разных наборах данных.<br /> <br /> === Чему вы научитесь? ===<br /> Вы узнаете, как устроены современные алгоритмы сжатия и научитесь создавать свои, а также научитесь измерять и оптимизировать производительность кода на C++.<br /> <br /> === Какие начальные требования? ===<br /> Владение C++<br /> <br /> === Какие будут использоваться технологии? ===<br /> Для измерения производительности мы будем применять perf<br /> <br /> === Темы вводных занятий ===<br /> На вводных занятиях мы рассмотрим устройство разных алгоритмов сжатия без потерь, их достоинства и недостатки.<br /> <br /> === Направления развития ===<br /> Алгоритм, победивший femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения словаря.<br /> <br /> === Критерии оценки ===<br /> 4-5: реализовано энтропийное кодирование<br /> 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности<br /> 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его<br /> <br /> === Ориентировочное расписание занятий ===<br /> СБ 9:00-12:00</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17247 2015-09-25T14:18:04Z

<p>Rkovalev: /* Что это за проект */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [https://ru.wikipedia.org/wiki/DynInst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> === Слайды ===<br /> [https://yadi.sk/i/O7AslJNLjKSw6 Лежат здесь.]<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу (трейсер), которая умеет логировать все события вызова функций и возврата из них.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер, используя отладочную информацию, выводит номер строки в файле, из которого было скомпилировано место вызова, а также значения аргументов и возвращаемое значение.<br /> * '''+2 балла'''. Поддерживаются многопоточные приложения.<br /> * '''+2 балла'''. Поддерживаются заинлайненные функции.<br /> * '''+N баллов'''. N = 4 * max(0, aver(1 - T&lt;sub&gt;tracer&lt;/sub&gt; / T&lt;sub&gt;callgrind&lt;/sub&gt;)) за обгон callgrind на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17245 2015-09-25T13:06:39Z

<p>Rkovalev: /* Что требуется */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [https://ru.wikipedia.org/wiki/DynInst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу (трейсер), которая умеет логировать все события вызова функций и возврата из них.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер, используя отладочную информацию, выводит номер строки в файле, из которого было скомпилировано место вызова, а также значения аргументов и возвращаемое значение.<br /> * '''+2 балла'''. Поддерживаются многопоточные приложения.<br /> * '''+2 балла'''. Поддерживаются заинлайненные функции.<br /> * '''+N баллов'''. N = 4 * max(0, aver(1 - T&lt;sub&gt;tracer&lt;/sub&gt; / T&lt;sub&gt;callgrind&lt;/sub&gt;)) за обгон callgrind на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17244 2015-09-25T12:58:35Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу (трейсер), которая умеет логировать все события вызова функций и возврата из них.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер, используя отладочную информацию, выводит номер строки в файле, из которого было скомпилировано место вызова, а также значения аргументов и возвращаемое значение.<br /> * '''+2 балла'''. Поддерживаются многопоточные приложения.<br /> * '''+2 балла'''. Поддерживаются заинлайненные функции.<br /> * '''+N баллов'''. N = 4 * max(0, aver(1 - T&lt;sub&gt;tracer&lt;/sub&gt; / T&lt;sub&gt;callgrind&lt;/sub&gt;)) за обгон callgrind на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17243 2015-09-25T12:58:04Z

<p>Rkovalev: /* Требования на зачет в конце 1-го модуля */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу (трейсер), которая умеет логировать все события вызова функций и возврата из них.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер, используя отладочную информацию, выводит номер строки в файле, из которого было скомпилировано место вызова, а также значения аргументов и возвращаемое значение.<br /> * '''+2 балла'''. Поддерживаются многопоточные приложения.<br /> * '''+N баллов'''. N = 4 * max(0, aver(1 - T&lt;sub&gt;tracer&lt;/sub&gt; / T&lt;sub&gt;callgrind&lt;/sub&gt;)) за обгон callgrind на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17242 2015-09-25T12:56:47Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер, используя отладочную информацию, выводит номер строки в файле, из которого было скомпилировано место вызова, а также значения аргументов и возвращаемое значение.<br /> * '''+2 балла'''. Поддерживаются многопоточные приложения.<br /> * '''+N баллов'''. N = 4 * max(0, aver(1 - T&lt;sub&gt;tracer&lt;/sub&gt; / T&lt;sub&gt;callgrind&lt;/sub&gt;)) за обгон callgrind на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17241 2015-09-25T12:46:59Z

<p>Rkovalev: /* Что это за проект */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+2 балла'''. Трейсер умеет выводить текущий стек вызовов в человекочитаемом формате.<br /> * '''+2 балла'''. Трейсер умеет выводить возвращаемое значение функции.<br /> * '''+2 балла'''. Трейсер поддерживает многопоточные приложения.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17240 2015-09-25T12:46:40Z

<p>Rkovalev: /* Что требуется */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной (можно даже взять callgrind и отрезать от него всё лишнее). Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать простой неинтерактивный дебагер, который будет выводить в файл историю вызовов функций в программе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+2 балла'''. Трейсер умеет выводить текущий стек вызовов в человекочитаемом формате.<br /> * '''+2 балла'''. Трейсер умеет выводить возвращаемое значение функции.<br /> * '''+2 балла'''. Трейсер поддерживает многопоточные приложения.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17239 2015-09-25T12:46:13Z

<p>Rkovalev: /* Введение */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Часто лучший способ понять, каким образом процесс пришёл в какое-то интересное состояние (например, в которое не должен был прийти никогда), - это проследить по шагам за его выполнением. Типичные способы, которые используются на практике: <br /> <br /> * К процессу можно присоединиться при помощи gdb и отследить его выполнение по шагам. Неудобства: во-первых, не всегда есть возможность присоединиться gdb в интерактивном режиме. Во-вторых, проблема может быть тяжело воспроизводимой, и шагов придётся делать очень много.<br /> * В программу можно добавить отладочную печать, и процесс в процессе работы будет записывать в поток своё состояние.<br /> <br /> Как можно добавить отладочную печать?<br /> * Например, можно модифицировать исходный код и пересобрать программу. Можно это сделать руками. Можно при помощи кодогенерации, так это делает, например, [http://ndevilla.free.fr/etrace/ etrace]. Недостаток: не всегда есть возможность пересобрать программу.<br /> * Можно воспользоваться системным вызовом [http://man7.org/linux/man-pages/man2/ptrace.2.html ptrace] и добавить [https://en.wikipedia.org/wiki/INT_%28x86_instruction%29#INT_3 software breakpoints] в интересующие места, как это делает [http://man7.org/linux/man-pages/man1/strace.1.html strace] или [http://www.gnu.org/software/gdb/ gdb]. Или даже ещё проще - написать [http://ndevilla.free.fr/etrace/ скрипт] для gdb. Недостаток этого подхода: это может быть очень медленно, если мы хотим трассировать большое количество событий.<br /> * Можно воспользоваться динамической линковкой через [http://samanbarghi.com/blog/2014/09/05/how-to-wrap-a-system-call-libc-function-in-linux/ LD_PRELOAD или ld --wrap], как это делает [http://man7.org/linux/man-pages/man1/ltrace.1.html ltrace]. Ограничение - нужна динамическая линковка.<br /> * И, наконец, мы можем на лету изменить код программы (это называется [https://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 инструментированием]). Так делает, например, [http://valgrind.org/docs/manual/cl-manual.html callgrind].<br /> <br /> === Что требуется ===<br /> Вам предлагается написать менее функциональный, но существенно более быстрый аналог callgrind с использованием инструментирования бинарного кода, воспользовавшись библиотекой [http://www.dyninst.org/dyninst DynInst] или аналогичной. Ваша программа должна будет выводить в поток все вызовы функций в исследуемом процессе.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать простой неинтерактивный дебагер, который будет выводить в файл историю вызовов функций в программе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+2 балла'''. Трейсер умеет выводить текущий стек вызовов в человекочитаемом формате.<br /> * '''+2 балла'''. Трейсер умеет выводить возвращаемое значение функции.<br /> * '''+2 балла'''. Трейсер поддерживает многопоточные приложения.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17236 2015-09-25T10:09:18Z

<p>Rkovalev: </p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать JIT компиляцию регулярных выражений, поддерживаемых re2, в машинный код x86-64.<br /> <br /> === Слайды ===<br /> [https://yadi.sk/d/ymlaks89jK69x Лежат тут.]<br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно написать библиотеку, которая использует [https://github.com/google/re2/ re2] для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат). <br /> <br /> Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17235 2015-09-25T10:08:21Z

<p>Rkovalev: </p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать JIT компиляцию регулярных выражений, поддерживаемых re2, в машинный код x86-64.<br /> <br /> [https://yadi.sk/d/ymlaks89jK69x А ещё у проекта есть презентация.]<br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно написать библиотеку, которая использует [https://github.com/google/re2/ re2] для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат). <br /> <br /> Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17232 2015-09-24T20:18:33Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Linux предоставляет ряд средств для отладки пользователем своих процессов. Например, можно посмотреть в память или регистры другого процесса или даже поменять там что-то. При помощи этих средств реализованы, к примеру, gdb и strace.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать простой неинтерактивный дебагер, который будет выводить в файл историю вызовов функций в программе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+2 балла'''. Трейсер умеет выводить текущий стек вызовов в человекочитаемом формате.<br /> * '''+2 балла'''. Трейсер умеет выводить возвращаемое значение функции.<br /> * '''+2 балла'''. Трейсер поддерживает многопоточные приложения.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17231 2015-09-24T20:17:27Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Linux предоставляет ряд средств для отладки пользователем своих процессов. Например, можно посмотреть в память или регистры другого процесса или даже поменять там что-то. При помощи этих средств реализованы, к примеру, gdb и strace.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать простой неинтерактивный дебагер, который будет выводить в файл историю вызовов функций в программе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+2 балла'''. Трейсер умеет выводить текущий стек вызовов в человекочитаемом формате.<br /> * '''+2 балла'''. Трейсер умеет выводить возвращаемое значение функции.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17229 2015-09-24T20:02:03Z

<p>Rkovalev: /* Что требуется */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать JIT компиляцию регулярных выражений, поддерживаемых re2, в машинный код x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно написать библиотеку, которая использует [https://github.com/google/re2/ re2] для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат). <br /> <br /> Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17228 2015-09-24T20:00:22Z

<p>Rkovalev: /* Требования на зачет в конце 1-го модуля */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно написать библиотеку, которая использует [https://github.com/google/re2/ re2] для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций для виртуальной машины в re2 и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Полученная конструкция работает корректно (re2 и re2jit на поддерживаемых регулярных выражениях дают один и тот же результат). <br /> <br /> Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17227 2015-09-24T19:55:55Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах (постараемся выбрать максимально приближенные к реальности).</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17226 2015-09-24T19:53:25Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, aver(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17225 2015-09-24T19:52:22Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, sum(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;) / sum(T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17224 2015-09-24T19:50:46Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, sum(1 - T&lt;sub&gt;re2jit&lt;/sub&gt; / T&lt;sub&gt;re2&lt;/sub&gt;)) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17223 2015-09-24T19:50:05Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, sum(1 - T_re2jit / T_re2)) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17222 2015-09-24T19:49:26Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, Sum(1 - Time(jit) / Time(re2))) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17221 2015-09-24T19:47:06Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, Sum(Time(re2) - Time(jit)) / Sum(Time(re2))) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17219 2015-09-24T19:45:07Z

<p>Rkovalev: /* Итоговая оценка */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''4 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''8 баллов'''. Все инструкции re2 VM компилируются в JIT.<br /> * '''+N баллов'''. N = 8 * max(0, (Time(re2) - Time(jit)) / Time(re2)) за обгон re2 на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17216 2015-09-24T19:43:19Z

<p>Rkovalev: /* Требования на зачет в конце 1-го модуля */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] регулярные выражения компилируются в инструкции виртуальной машины, реализующей алгоритм Томпсона. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины и может при помощи [http://yasm.tortall.net/ libyasm], [http://sljit.sourceforge.net/ sljit] или [http://www.gnu.org/software/libjit/ libjit] компилировать в x86_64 и запускать какое-то непустое подмножество этих инструкций (LLVM плохо, т.к. компиляция должна быть максимально быстрой). Пример того, как можно запустить JIT код, описан в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction этой статье].<br /> <br /> === Итоговая оценка ===<br /> * '''3 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''7 баллов'''. Байткод компилируется в машинный код, машинный код работает правильно.<br /> * '''+1 балл'''. Реализована поддержка юникода и capturing groups (захватывающих скобок).<br /> * '''+N баллов'''. N = 8 * max(0, (Time(re2) - Time(jit)) / Time(re2)) на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17208 2015-09-24T17:00:28Z

<p>Rkovalev: /* Требования на зачет в конце 1-го модуля */</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> В [https://github.com/google/re2/ re2] реализована компиляция регулярных выражений в инструкции виртуальной машины. Нужно написать библиотеку, которая использует re2 для синтаксического разбора регулярных выражений, получает из неё представление регулярного выражения в виде инструкций этой виртуальной машины, умеет при помощи [http://yasm.tortall.net/ libyasm] компилировать и запускать какое-то непустое подмножество этих инструкций. Например, так, как это описано в [http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction статье].<br /> <br /> === Итоговая оценка ===<br /> * '''3 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''7 баллов'''. Байткод компилируется в машинный код, машинный код работает правильно.<br /> * '''+1 балл'''. Реализована поддержка юникода и capturing groups (захватывающих скобок).<br /> * '''+N баллов'''. N = 8 * max(0, (Time(re2) - Time(jit)) / Time(re2)) на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B&diff=17176 2015-09-20T23:18:42Z

<p>Rkovalev: /* Проектная работа */</p> <hr /> <div>= Список литературы =<br /> <br /> # Э. Таненбаум, Х. Бос. Современные операционные системы. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-496-01395-6<br /> # Э. Таненбаум, Т. Остин. Архитектура компьютера. 6-е издание. СПб.: Питер, 2015. ISBN 978-5-496-00337-7<br /> # Д. Паттерсон, Дж. Хеннесси. Архитектура компьютера и проектирование компьютерных систем. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-459-00291-1<br /> # Р. Лав. Ядро Linux: описание процесса разработки. 3-е издание. М.: OOO И.Д. Вильямс, 2015. ISBN 978-5-8459-1944-1<br /> # Р. Э. Брайант, Д. Р. О'Халларон. Компьютерные системы: архитектура и программирование. СПб.: БХВ-Петербург, 2005. ISBN 5-94157-433-9<br /> # С. А. Раго, У. Р. Стивенс. UNIX. Профессиональное программирование. 3-е издание. М.: Символ-Плюс, 2014. ISBN 978-5-93286-216-2<br /> <br /> = Ссылки на материалы =<br /> <br /> [https://github.com/hseos/hseos-course/tree/master/00-lectures Слайды лекций]<br /> <br /> [https://github.com/hseos/hseos-course/ Репозиторий с материалами семинарских занятий]<br /> <br /> = Проектная работа =<br /> <br /> [[Эмулятор микроконтроллера ATtiny13A]]<br /> <br /> [[Веб-сервер с функциональностью CGI]]<br /> <br /> [[КС:2015:Проект:Memcached|Сервер Memcached]]<br /> <br /> [[КС:2015:Проект:Shell|Интерпретатор командной строки (shell)]]<br /> <br /> [[КС:2015:Проект:Cachesim|Эмулятор кеш-памяти]]<br /> <br /> [[КС:2015:Проект:MC|Файловый менеджер (mc)]]<br /> <br /> [[КС:2015:Проект:Htop|Менеджер процессов]]<br /> <br /> [[КС:2015:Проект:RT11-fuse|Драйвер файловой системы RT-11]]<br /> <br /> [[КС:2015:Проект:debuger|Неинтерактивный отладчик]]<br /> <br /> [[КС:2015:Проект:jit|JIT компилятор регулярных выражений]]<br /> <br /> [[КС:2015:Проект:fuse-p7zip|Файловая система из 7z-архива]]<br /> <br /> [[КС:2015:Проект:rpmdb-alien-repos-sync|Синхронизация базы данных RPM из стороннимх пакетных менеджеров]]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B&diff=17175 2015-09-20T23:18:21Z

<p>Rkovalev: /* Проектная работа */</p> <hr /> <div>= Список литературы =<br /> <br /> # Э. Таненбаум, Х. Бос. Современные операционные системы. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-496-01395-6<br /> # Э. Таненбаум, Т. Остин. Архитектура компьютера. 6-е издание. СПб.: Питер, 2015. ISBN 978-5-496-00337-7<br /> # Д. Паттерсон, Дж. Хеннесси. Архитектура компьютера и проектирование компьютерных систем. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-459-00291-1<br /> # Р. Лав. Ядро Linux: описание процесса разработки. 3-е издание. М.: OOO И.Д. Вильямс, 2015. ISBN 978-5-8459-1944-1<br /> # Р. Э. Брайант, Д. Р. О'Халларон. Компьютерные системы: архитектура и программирование. СПб.: БХВ-Петербург, 2005. ISBN 5-94157-433-9<br /> # С. А. Раго, У. Р. Стивенс. UNIX. Профессиональное программирование. 3-е издание. М.: Символ-Плюс, 2014. ISBN 978-5-93286-216-2<br /> <br /> = Ссылки на материалы =<br /> <br /> [https://github.com/hseos/hseos-course/tree/master/00-lectures Слайды лекций]<br /> <br /> [https://github.com/hseos/hseos-course/ Репозиторий с материалами семинарских занятий]<br /> <br /> = Проектная работа =<br /> <br /> [[Эмулятор микроконтроллера ATtiny13A]]<br /> <br /> [[Веб-сервер с функциональностью CGI]]<br /> <br /> [[КС:2015:Проект:Memcached|Сервер Memcached]]<br /> <br /> [[КС:2015:Проект:Shell|Интерпретатор командной строки (shell)]]<br /> <br /> [[КС:2015:Проект:Cachesim|Эмулятор кеш-памяти]]<br /> <br /> [[КС:2015:Проект:MC|Файловый менеджер (mc)]]<br /> <br /> [[КС:2015:Проект:Htop|Менеджер процессов]]<br /> <br /> [[КС:2015:Проект:RT11-fuse|Драйвер файловой системы RT-11]]<br /> <br /> [[КС:2015:Проект:debuger|Трассировщик вызовов функций]]<br /> <br /> [[КС:2015:Проект:jit|JIT компилятор регулярных выражений]]<br /> <br /> [[КС:2015:Проект:fuse-p7zip|Файловая система из 7z-архива]]<br /> <br /> [[КС:2015:Проект:rpmdb-alien-repos-sync|Синхронизация базы данных RPM из стороннимх пакетных менеджеров]]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B&diff=17174 2015-09-20T23:17:43Z

<p>Rkovalev: /* Проектная работа */</p> <hr /> <div>= Список литературы =<br /> <br /> # Э. Таненбаум, Х. Бос. Современные операционные системы. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-496-01395-6<br /> # Э. Таненбаум, Т. Остин. Архитектура компьютера. 6-е издание. СПб.: Питер, 2015. ISBN 978-5-496-00337-7<br /> # Д. Паттерсон, Дж. Хеннесси. Архитектура компьютера и проектирование компьютерных систем. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-459-00291-1<br /> # Р. Лав. Ядро Linux: описание процесса разработки. 3-е издание. М.: OOO И.Д. Вильямс, 2015. ISBN 978-5-8459-1944-1<br /> # Р. Э. Брайант, Д. Р. О'Халларон. Компьютерные системы: архитектура и программирование. СПб.: БХВ-Петербург, 2005. ISBN 5-94157-433-9<br /> # С. А. Раго, У. Р. Стивенс. UNIX. Профессиональное программирование. 3-е издание. М.: Символ-Плюс, 2014. ISBN 978-5-93286-216-2<br /> <br /> = Ссылки на материалы =<br /> <br /> [https://github.com/hseos/hseos-course/tree/master/00-lectures Слайды лекций]<br /> <br /> [https://github.com/hseos/hseos-course/ Репозиторий с материалами семинарских занятий]<br /> <br /> = Проектная работа =<br /> <br /> [[Эмулятор микроконтроллера ATtiny13A]]<br /> <br /> [[Веб-сервер с функциональностью CGI]]<br /> <br /> [[КС:2015:Проект:Memcached|Сервер Memcached]]<br /> <br /> [[КС:2015:Проект:Shell|Интерпретатор командной строки (shell)]]<br /> <br /> [[КС:2015:Проект:Cachesim|Эмулятор кеш-памяти]]<br /> <br /> [[КС:2015:Проект:MC|Файловый менеджер (mc)]]<br /> <br /> [[КС:2015:Проект:Htop|Менеджер процессов]]<br /> <br /> [[КС:2015:Проект:RT11-fuse|Драйвер файловой системы RT-11]]<br /> <br /> [[КС:2015:Проект:debuger|Простой неинтерактивный дебагер]]<br /> <br /> [[КС:2015:Проект:jit|JIT компилятор регулярных выражений]]<br /> <br /> [[КС:2015:Проект:fuse-p7zip|Файловая система из 7z-архива]]<br /> <br /> [[КС:2015:Проект:rpmdb-alien-repos-sync|Синхронизация базы данных RPM из стороннимх пакетных менеджеров]]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:debuger&diff=17173 2015-09-20T23:17:04Z

<p>Rkovalev: Новая страница: «== Что это за проект == === Введение === Linux предоставляет ряд средств для отладки пользовате…»</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> Linux предоставляет ряд средств для отладки пользователем своих процессов. Например, можно посмотреть в память или регистры другого процесса или даже поменять там что-то. При помощи этих средств реализованы, к примеру, gdb и strace.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать простой неинтерактивный дебагер, который будет выводить в файл историю вызовов функций в программе.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроены отладчики.<br /> <br /> 2. Узнаете, как устроена память процесса.<br /> <br /> 3. Подружитесь с эльфом и дварфом.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать программу, которая умеет трейсить вызовы функций и выводить их имена в файл.<br /> <br /> === Итоговая оценка ===<br /> * '''3 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''7 баллов'''. Трейсер выводит имена вызываемых функций, а также, используя отладочную информацию в отлаживаемом бинарнике, выводит значения параметров, с которыми эта функция была вызвана, номер строки и название файла исходого кода, из которых было скомпилировано место вызова.<br /> * '''+1 балл'''. Трейсер умеет выводить текущий стек вызовов.<br /> * '''+2 балла'''. Поддерживаются многопоточные программы.<br /> * '''+2 балла'''. Трейсер умеет отслеживать переключение контекста в корутинах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%A1:2015:%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82:jit&diff=17172 2015-09-20T22:33:36Z

<p>Rkovalev: Новая страница: «== Что это за проект == === Введение === JIT компиляция (Just In Time, ещё называют динамической) - это…»</p> <hr /> <div>== Что это за проект ==<br /> <br /> === Введение ===<br /> JIT компиляция (Just In Time, ещё называют динамической) - это компиляция виртуальной машиной программы на интерпретируем байткоде в машинный код в процессе её выполнения. Позволяет увеличить скорость выполнения интерпретируемой программы. Применяется, в частности, в виртуальных машинах pypy и java hotspot.<br /> <br /> === Что требуется ===<br /> Вам предлагается реализовать быструю библиотеку регулярных выражений, которая умеет компилировать регулярные выражения непосредственно в инструкции x86-64.<br /> <br /> == Чему вы научитесь ==<br /> 1. Узнаете, как устроена JIT компиляция.<br /> <br /> 2. Научитесь профилировать код и искать узкие места в производительности.<br /> <br /> 3. Научитесь писать интерпретаторы с JIT.<br /> <br /> == Начальные требования ==<br /> 1. Технический английский язык.<br /> <br /> 2. Знание C++.<br /> <br /> 3. Любознательность.<br /> <br /> == Критерии оценивания ==<br /> <br /> === Требования на зачет в конце 1-го модуля ===<br /> Нужно будет реализовать библиотеку регулярных выражений, которая умеет по регулярному выражению в диалекте POSIX extended построить автомат, скомпилировать этот автомат в байткод и затем его выполнить. Также программа должна уметь дампить байткод и считывать его из дампа.<br /> <br /> === Итоговая оценка ===<br /> * '''3 балла'''. Реализованы требования на зачёт в конце первого модуля.<br /> * '''7 баллов'''. Байткод компилируется в машинный код, машинный код работает правильно.<br /> * '''+1 балл'''. Реализована поддержка юникода и capturing groups (захватывающих скобок).<br /> * '''+N баллов'''. N = 8 * max(0, (Time(re2) - Time(jit)) / Time(re2)) на предложенных тестах.</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B&diff=17154 2015-09-17T14:33:31Z

<p>Rkovalev: </p> <hr /> <div>= Список литературы =<br /> <br /> # Э. Таненбаум, Х. Бос. Современные операционные системы. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-496-01395-6<br /> # Э. Таненбаум, Т. Остин. Архитектура компьютера. 6-е издание. СПб.: Питер, 2015. ISBN 978-5-496-00337-7<br /> # Д. Паттерсон, Дж. Хеннесси. Архитектура компьютера и проектирование компьютерных систем. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-459-00291-1<br /> # Р. Лав. Ядро Linux: описание процесса разработки. 3-е издание. М.: OOO И.Д. Вильямс, 2015. ISBN 978-5-8459-1944-1<br /> # Р. Э. Брайант, Д. Р. О'Халларон. Компьютерные системы: архитектура и программирование. СПб.: БХВ-Петербург, 2005. ISBN 5-94157-433-9<br /> # С. А. Раго, У. Р. Стивенс. UNIX. Профессиональное программирование. 3-е издание. М.: Символ-Плюс, 2014. ISBN 978-5-93286-216-2<br /> <br /> = Ссылки на материалы =<br /> <br /> [https://github.com/hseos/hseos-course/tree/master/00-lectures Слайды лекций]<br /> <br /> [https://github.com/hseos/hseos-course/ Репозиторий с материалами семинарских занятий]<br /> <br /> = Проектная работа =<br /> <br /> [[Эмулятор микроконтроллера ATtiny13A]]<br /> <br /> [[Веб-сервер с функциональностью CGI]]<br /> <br /> [[КС:2015:Проект:Memcached|Сервер Memcached]]<br /> <br /> [[КС:2015:Проект:Shell|Интерпретатор командной строки (shell)]]<br /> <br /> [[КС:2015:Проект:Cachesim|Эмулятор кеш-памяти]]<br /> <br /> [[КС:2015:Проект:MC|Файловый менеджер (mc)]]<br /> <br /> [[КС:2015:Проект:RT11-fuse|Драйвер файловой системы RT-11]]<br /> <br /> [[КС:2015:Проект:allocator|Быстрый аллокатор оперативной памяти (аналог jemalloc / tcmalloc)]]<br /> <br /> [[КС:2015:Проект:lock-free|Многопоточная структура данных без блокировок (LF очередь / RCU / ???)]]<br /> <br /> [[КС:2015:Проект:coroutines|Библиотека корутин на C]]<br /> <br /> [[КС:2015:Проект:tcp-over-udp|Простой протокол надёжной доставки данных (подмножество TCP) поверх UDP]]<br /> <br /> [[КС:2015:Проект:debuger|Простой неинтерактивный дебагер]]<br /> <br /> [[КС:2015:Проект:jit|JIT компилятор регулярных выражений]]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B&diff=17153 2015-09-16T22:42:17Z

<p>Rkovalev: /* Проектная работа */</p> <hr /> <div>= Список литературы =<br /> <br /> # Э. Таненбаум, Х. Бос. Современные операционные системы. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-496-01395-6<br /> # Э. Таненбаум, Т. Остин. Архитектура компьютера. 6-е издание. СПб.: Питер, 2015. ISBN 978-5-496-00337-7<br /> # Д. Паттерсон, Дж. Хеннесси. Архитектура компьютера и проектирование компьютерных систем. 4-е издание. СПб.: Питер, 2015. ISBN 978-5-459-00291-1<br /> # Р. Лав. Ядро Linux: описание процесса разработки. 3-е издание. М.: OOO И.Д. Вильямс, 2015. ISBN 978-5-8459-1944-1<br /> # Р. Э. Брайант, Д. Р. О'Халларон. Компьютерные системы: архитектура и программирование. СПб.: БХВ-Петербург, 2005. ISBN 5-94157-433-9<br /> # С. А. Раго, У. Р. Стивенс. UNIX. Профессиональное программирование. 3-е издание. М.: Символ-Плюс, 2014. ISBN 978-5-93286-216-2<br /> <br /> = Ссылки на материалы =<br /> <br /> [https://github.com/hseos/hseos-course/tree/master/00-lectures Слайды лекций]<br /> <br /> [https://github.com/hseos/hseos-course/ Репозиторий с материалами семинарских занятий]<br /> <br /> = Проектная работа =<br /> <br /> [[Эмулятор микроконтроллера ATtiny13A]]<br /> <br /> [[Веб-сервер с функциональностью CGI]]<br /> <br /> [[КС:2015:Проект:Memcached|Сервер Memcached]]<br /> <br /> [[КС:2015:Проект:Shell|Интерпретатор командной строки (shell)]]<br /> <br /> [[КС:2015:Проект:Cachesim|Эмулятор кеш-памяти]]<br /> <br /> [[КС:2015:Проект:MC|Файловый менеджер (mc)]]<br /> <br /> [[КС:2015:Проект:RT11-fuse|Драйвер файловой системы RT-11]]<br /> <br /> [[КС:2015:Проект:allocator|Аллокатор памяти]]<br /> <br /> [[КС:2015:Проект:lock-free|Многопоточная структура данных без блокировок]]<br /> <br /> [[КС:2015:Проект:coroutines|Сопрограмма]]<br /> <br /> [[КС:2015:Проект:tcp-over-udp|TCP поверх UDP]]<br /> <br /> [[КС:2015:Проект:debuger|Простой дебагер]]<br /> <br /> [[КС:2015:Проект:jit|JIT компилятор]]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%9F%D0%BE%D0%B4%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_106-1&diff=1307 2015-01-18T23:35:09Z

<p>Rkovalev: </p> <hr /> <div>[https://bitbucket.org/velavokr/hse-2015-106-1-algorithms-and-data-structures/src Все материалы семинаров будут выкладываться на bitbucket]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%9F%D0%BE%D0%B4%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_106-1&diff=1305 2015-01-18T23:17:26Z

<p>Rkovalev: Новая страница: «[https://bitbucket.org/velavokr/hse-2015-106-1-algorithms-and-data-structures/src/c91e7f275f74?at=master Все материалы семинаров будут…»</p> <hr /> <div>[https://bitbucket.org/velavokr/hse-2015-106-1-algorithms-and-data-structures/src/c91e7f275f74?at=master Все материалы семинаров будут выкладываться на bitbucket]</div>

Rkovalev https://wiki.cs.hse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_2016&diff=1304 2015-01-18T23:15:30Z

<p>Rkovalev: 106-1</p> <hr /> <div>== Лекции ==<br /> '''13 января:''' Сортировка вставкой и слиянием. Использование инварианта цикла при доказательстве корректности сортировки вставкой. Θ- и ''O''-обозначения. Оценка сложности алгоритмов. Рекуррентные соотношения.<br /> <br /> '''16 января:''' ''О''-, ''o''-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой.<br /> <br /> == Семинары ==<br /> [[Алгоритмы и структуры данных. Подгруппа 101-1|Подгруппа 101-1.]]&lt;br&gt;<br /> [[Алгоритмы и структуры данных. Подгруппа 105-1|Подгруппа 105-1.]]&lt;br&gt;<br /> [[Алгоритмы и структуры данных. Подгруппа 106-1|Подгруппа 106-1.]]&lt;br&gt;<br /> <br /> == Рекомендуемая литература ==<br /> # [http://e-maxx.ru/bookz/files/cormen.pdf Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ]<br /> # [https://dl.dropboxusercontent.com/u/829163/draft.pdf Дасгупты, Пападимитриу, Вазирани. Алгоритмы] ([http://beust.com/algorithms.pdf оригинал] | [http://biblio.mccme.ru/node/5066/shop купить])</div>

Rkovalev