Без map пришлось бы либо хранить в векторе всегда отсортированные по ключу пары (и тогда поиск по конкретному ключу займёт O(log(N)) времени, где N - длина вектора), затрачивая существенное время (O(N) на сдвиг) на вставку, либо вставлять как попало (O(1)) и делать полный пересбор (O(N)), пока не найдём нужный элемент.
map позволяет получить амортизированную сложность O(1) как на вставку, так и на поиск.
компилятор обычно генерирует машинный код, а не ассемблерную программу
Скорее всего тут недостаточно контекста, и всё зависит от того, что понимается под терминами "компилятор" и "программа".
Самый обычный (поставляется вместе с ОС) GCC 13.3.0 на моей машине при выполнении "gcc hello.c" ведёт себя так (это можно проверить с помощью strace -f или gcc -v):
Запускает компилятор "cc1", который читает с диска hello.c и записывает временный файл на языке ассемблера в $TMPDIR со случайным именем с суффиксом ".s".
Запускает ассемблер "as", который читает временный файл из п. 1 и записывает новый временный объектный файл в $TMPDIR со случайным именем с суффиксом ".o".
Запускает обёртку "collect2", которая запускает компоновщик "ld".
ld собирает программу из crt*.o и файла, полученного в п. 2, порождая динамически (с использованием загрузчика ld-linux-aarch64.so.1) слинкованный (с libc.so.6) исполняемый файл с именем a.out.
Являются ли компилятором "gcc" и/или (только) "cc1"? Является ли ассемблерной программой файл .s из п.1?
Чем операционная семантика отличается от денотационной, и они обе - от синтаксиса.
Если не секрет, то как вы объясняете это, чтобы студент понял, не заставляя написать компилятор? И сколько времени на это уходит?
Объяснить, что такое "возвращаемое значение" можно с двух сторон, используя две разные модели. В любом случае, ответом на вопрос "кто возвращает" будет "функция".
Можно провести аналогию со школьной математикой, где функции задаются либо таблично, либо формулами. Там возвращаемое значение - элемент из области значений функции. Пусть f(x)=sin(x)/x, тогда f(1.57) "вернёт" примерно 0.64. "Куда возвращает" - в место использования; если у нас есть формула f(1.57)*2+1, то в ней мы можем заменить f(1.57) на 0.64, произведя вычисления согласно определению f. Ответ на вопрос "зачем" как всегда самый сложный. Функция f: A -> B позволяет нам абстрагироваться от конкретного способа связи элементов A с элементами B. Возвращая значение (элемент из B), мы выполняем обратную операцию для некоторого частного случая (элемента из A).
Подстановка f в выражение
Пусть f(x)=3*x.
Вычислим значение выражения f(5)+1.
--
f(5) + 1 =
= (3*5) + 1 = то, что в скобках "вернула" нам f
= 15 + 1 =
= 16
Можно привести пример конкретного calling convention. Вызванная функция ожидает, что в непрерывном куске памяти (на начало который указывает один из регистров) находятся её аргументы, перед которыми записан адрес той инструкции, с которой будет продолжаться выполнение (адрес возврата - "куда возвращает"), когда функция выполнит свою работу. Одним из эффектов работы функции может быть изменение регистра возвращаемого значения, которое ожидается в месте возврата. "Зачем" - чтобы передать в место вызова явный результат проделанной работы.
Процесор i386, соглашение cdecl
; У нас есть две функции. main вызывает triple, которая возвращает
; утроенное значение своего целого аргуметна.
; main вызывает triple от 5 и увеличивает результат на 1.
main:
; Положим число 5 на стек.
push 5
; Теперь регистр ESP указывает на место в памяти, где лежит
; число 5. Например, ESP=0xff8113f8, а по адресу
; 0xff8113f8 лежат биты 00000101 00000000 00000000 00000000
; Вызываем функцию triple.
call triple
; Перед вызовом call положит на стек адрес инструкции,
; следующей за call. Это сдвинет ESP на 4 вниз, и запишет
; адрес возврата по адресу, соответствующему новому значению
; ESP. Если следовать предыдущему примеру, а адрес инструкции
; call (строка 12) равен 0xf7ee0240 то теперь
; ESP=0xff8113f4, а по адресу 0xff8113f4 лежат биты
; 11110111 11101110 00000010 01000101 00000101 00000000 00000000 00000000
; Вот в это место произойдёт возврат из triple, когда оттуда
; сделают ret (строка 48). И сейчас в EAX лежит число 15, то есть
; утроенное значение 5. Осталось увеличить EAX на 1.
inc eax
; EAX=16. Теперь вызовем отладчик в демонстративных целях:
int3
; и завершим работу программы.
ret
triple:
; Прочитаем аргумент из стека в регистр EAX.
mov eax, [esp+4]
; Скопируем его значение в EDX.
mov edx, eax
; Удвоим EDX.
add edx, edx
; И сложим наш аргумент с его удвоенной копией.
add eax, edx
; Готово, теперь в EAX лежит утроенное знечение. Работа
; завершена, можно возвращаться в место вызова.
ret
; Что сделает ret? Прочитает то, что лежит по адресу,
; на который указывает ESP, и вернёт нас по нему (обратно),
; одновременно увеличив ESP на 4.
В данном примере машина выполнит инструкции в следующем порядке (укзааны номера строк) - 7, 13, 35, 38, 41, 44, 48, 25, 28, 31.
Для контроля понимания можно посчитать на бумажке результат рекурсивной функции, используя обе модели. Например из определения "f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)" получить значение для f(10) - тут должно получиться 55.
Возможно для наглядности стоит сделать какую-нибудь анимацию, как происходит вызов, передача аргументов и возврат значения.
Большое или маленькое изменение произойдёт, если мы изменим первый байт? Ещё помогает то, что в названиях платформ (mips64el) используют "перевёрнутый" суффикс "el" (endian little).
Только с cmov не получится, нужна либо хоть какая-нибудь арифметика, либо перед запуском программы память должна быть заполнена какой-нибудь хитрой табличкой, а cmov должен уметь делать load/store с displacement. Для машин с одной инструкцией (OISC) чаще применяют subleq A, B, C, которая делает *B = *B - *A; if (*B <= 0) { IP = C; } else { IP++; }
Коллега показывал свою "wife approved" оптоволоконную домашнюю сеть - он нашёл довольно тонкие прозрачные кабели, которые закрепил на стене кусочками прозрачного скотча. Если бы он просто показал мне фотографию, и не сказал, куда смотреть, то я бы ничего и не заметил - выглядит, как просто обычная стена.
Мне нравился Samsung Galaxy Spica с Android 2.3 - особенно хороши были аппаратные кнопки, с которых можно управлять смартфоном зимой. Увы, современный софт и веб-страницы он уже не потянет.
В ChromeOS софт можно доставить, как во встроенный слой совместимости с Android через Google Play, так и в виде Chrome Extensions. А включив Developer Mode, ChromeOS превращается в Gentoo.
Что самое забавное, инструкция bswap не нужна для загрузки ресурсов. Она нужна для функции, которая вычисляет CRC от константной строки, и если она не совпала с ожидаемым значением, развалить процесс.
Вот эта строка: "!!!! BUILD engine&tools programmed by Ken Silverman of E.G. RI. (c) Copyright 1995 Ken Silverman. Summary: BUILD = Ken. !!!!"
Если это так для этого мини ПК, то стоит собрать как можно больше информации о железе. У coreboot есть неплохой набор инструкций на этот случай - можно выполнить всё из https://www.coreboot.org/Motherboard_Porting_Guide до запуска flashrom.
Узнать, что используется в качестве звуковой карты, wi-fi и bluetooth можно из выводов команд lspci -nn и lsusb (которые в OpenWrt есть в пакетах pciutils и usbutils соответственно).
Обычно не нужно разблокировать телефон для выключения - достаточно немного подержать кнопку питания и подтвердить отключение.
Тут скорее дело в том, что человек понимая, что скоро останется без связи, хочет быстро проверить, нет ли для него каких-нибудь сообщений, на которые нужно немедленно отреагировать.
I2P в таком сценарии может ещё использоваться для обхода NAT и firewall, за которыми находится VPN-сервер.
Без map пришлось бы либо хранить в векторе всегда отсортированные по ключу пары (и тогда поиск по конкретному ключу займёт O(log(N)) времени, где N - длина вектора), затрачивая существенное время (O(N) на сдвиг) на вставку, либо вставлять как попало (O(1)) и делать полный пересбор (O(N)), пока не найдём нужный элемент.
map позволяет получить амортизированную сложность O(1) как на вставку, так и на поиск.
Скорее всего тут недостаточно контекста, и всё зависит от того, что понимается под терминами "компилятор" и "программа".
Самый обычный (поставляется вместе с ОС) GCC 13.3.0 на моей машине при выполнении "gcc hello.c" ведёт себя так (это можно проверить с помощью strace -f или gcc -v):
Запускает компилятор "cc1", который читает с диска hello.c и записывает временный файл на языке ассемблера в $TMPDIR со случайным именем с суффиксом ".s".
Запускает ассемблер "as", который читает временный файл из п. 1 и записывает новый временный объектный файл в $TMPDIR со случайным именем с суффиксом ".o".
Запускает обёртку "collect2", которая запускает компоновщик "ld".
ld собирает программу из crt*.o и файла, полученного в п. 2, порождая динамически (с использованием загрузчика ld-linux-aarch64.so.1) слинкованный (с libc.so.6) исполняемый файл с именем a.out.
Являются ли компилятором "gcc" и/или (только) "cc1"? Является ли ассемблерной программой файл .s из п.1?
Если не секрет, то как вы объясняете это, чтобы студент понял, не заставляя написать компилятор? И сколько времени на это уходит?
Объяснить, что такое "возвращаемое значение" можно с двух сторон, используя две разные модели. В любом случае, ответом на вопрос "кто возвращает" будет "функция".
Можно провести аналогию со школьной математикой, где функции задаются либо таблично, либо формулами. Там возвращаемое значение - элемент из области значений функции. Пусть f(x)=sin(x)/x, тогда f(1.57) "вернёт" примерно 0.64. "Куда возвращает" - в место использования; если у нас есть формула f(1.57)*2+1, то в ней мы можем заменить f(1.57) на 0.64, произведя вычисления согласно определению f. Ответ на вопрос "зачем" как всегда самый сложный. Функция f: A -> B позволяет нам абстрагироваться от конкретного способа связи элементов A с элементами B. Возвращая значение (элемент из B), мы выполняем обратную операцию для некоторого частного случая (элемента из A).
Подстановка f в выражение
Можно привести пример конкретного calling convention. Вызванная функция ожидает, что в непрерывном куске памяти (на начало который указывает один из регистров) находятся её аргументы, перед которыми записан адрес той инструкции, с которой будет продолжаться выполнение (адрес возврата - "куда возвращает"), когда функция выполнит свою работу. Одним из эффектов работы функции может быть изменение регистра возвращаемого значения, которое ожидается в месте возврата. "Зачем" - чтобы передать в место вызова явный результат проделанной работы.
Процесор i386, соглашение cdecl
В данном примере машина выполнит инструкции в следующем порядке (укзааны номера строк) - 7, 13, 35, 38, 41, 44, 48, 25, 28, 31.
Для контроля понимания можно посчитать на бумажке результат рекурсивной функции, используя обе модели. Например из определения "f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)" получить значение для f(10) - тут должно получиться 55.
Возможно для наглядности стоит сделать какую-нибудь анимацию, как происходит вызов, передача аргументов и возврат значения.
Большое или маленькое изменение произойдёт, если мы изменим первый байт? Ещё помогает то, что в названиях платформ (mips64el) используют "перевёрнутый" суффикс "el" (endian little).
А как они находят соцсети сотрудника, и что будет, если сотрудник на подобный вопрос ответит "это не моя страница"?
Только с
cmovне получится, нужна либо хоть какая-нибудь арифметика, либо перед запуском программы память должна быть заполнена какой-нибудь хитрой табличкой, а cmov должен уметь делать load/store с displacement. Для машин с одной инструкцией (OISC) чаще применяютsubleq A, B, C, которая делает*B = *B - *A; if (*B <= 0) { IP = C; } else { IP++; }А как именно Бабаян уничтожал процессоры "Эльбрус"? И почему у него не получилось?
Коллега показывал свою "wife approved" оптоволоконную домашнюю сеть - он нашёл довольно тонкие прозрачные кабели, которые закрепил на стене кусочками прозрачного скотча. Если бы он просто показал мне фотографию, и не сказал, куда смотреть, то я бы ничего и не заметил - выглядит, как просто обычная стена.
Мне нравился Samsung Galaxy Spica с Android 2.3 - особенно хороши были аппаратные кнопки, с которых можно управлять смартфоном зимой. Увы, современный софт и веб-страницы он уже не потянет.
В ChromeOS софт можно доставить, как во встроенный слой совместимости с Android через Google Play, так и в виде Chrome Extensions. А включив Developer Mode, ChromeOS превращается в Gentoo.
Что самое забавное, инструкция bswap не нужна для загрузки ресурсов. Она нужна для функции, которая вычисляет CRC от константной строки, и если она не совпала с ожидаемым значением, развалить процесс.
Вот эта строка: "!!!! BUILD engine&tools programmed by Ken Silverman of E.G. RI. (c) Copyright 1995 Ken Silverman. Summary: BUILD = Ken. !!!!"
У PS3 одноядерный двухпоточный PowerPC и 8 SPE (из которых один отключён производителем в процессе отбраковки, и ещё один зарезервирован системой).
А чем это принципиально отличается от ситуации, когда я не могу купить квартиру, и мне приходится брать ипотеку?
Если это так для этого мини ПК, то стоит собрать как можно больше информации о железе. У coreboot есть неплохой набор инструкций на этот случай - можно выполнить всё из https://www.coreboot.org/Motherboard_Porting_Guide до запуска flashrom.
Узнать, что используется в качестве звуковой карты, wi-fi и bluetooth можно из выводов команд
lspci -nnиlsusb(которые в OpenWrt есть в пакетахpciutilsиusbutilsсоответственно).C^X^X^X
Это уже было в 8086: https://www.reenigne.org/blog/8086-microcode-disassembled/
Обычно не нужно разблокировать телефон для выключения - достаточно немного подержать кнопку питания и подтвердить отключение.
Тут скорее дело в том, что человек понимая, что скоро останется без связи, хочет быстро проверить, нет ли для него каких-нибудь сообщений, на которые нужно немедленно отреагировать.
Томас Андерсон был джуном.