Использование неинициализированной памяти c как исправить
Я изучаю C++, и я узнал, что указатели, если оставить неинициализированные, могут указывать на случайные места в памяти и создавать проблемы, которые память может использоваться какой-то другой программой.
Теперь, если это так, мы никогда не должны иметь эту строку в любой части нашего кода:
вместо этого мы должны иметь что-то вроде
пожалуйста, предложите, потому что я видел первую строку ( int* ptr; ) во многих книгах, поэтому я получаю это сомнение. Если возможно, приведите также несколько примеров.
это приведет к ptr указать NULL который вы можете явно проверить как значение по умолчанию / неинициализированное. Это предотвращает описанную вами проблему, но неосторожный программист все равно может случайно разыменовать нулевой указатель без проверки, вызывая неопределенное поведение.
главное преимущество ваше удобство для проверки ли ptr был или не был инициализирован ни к чему, т. е.:
так как это довольно идиоматично, его довольно опасно не инициализировать указатель на NULL . Указатель будет инициализирован ненулевым значением мусора, которое на самом деле не указывает на что-либо реальное. Хуже всего, что проверка выше пройдет, что вызовет еще худшие проблемы, если так случится, что адрес в указателе-это память, к которой вы можете получить легальный доступ. В некоторых встроенных средах вы можете получить доступ к любой части памяти, поэтому вы можете случайно повредить случайные части памяти или случайные части вашего выполнения код.
всегда инициализируйте переменные.
иногда вы можете инициализировать NULL , но большую часть времени вы должны иметь возможность инициализировать указатель стоимостью предполагается провести. Объявите переменные как можно позже и инициализируйте их в этот момент, а не на 15 строках ниже в коде.
определенно не гарантируется инициализация значения указателя на что-либо в частности. Строка:
инициализирует указатель на точку для обращения к нулю, который на практике никогда не будет содержать ничего полезного и который будет обычно проверяться как недопустимое значение указателя.
конечно, все еще возможно, как сказал Дуг т., попытаться использовать этот указатель, не проверяя его, и поэтому он будет крушение все равно.
явная инициализация в NULL имеет то преимущество, что разыменование указателя перед установкой его на что-то полезное приведет к сбою, что на самом деле хорошо, потому что это предотвращает "случайную" работу кода при маскировке серьезной ошибки.
всегда лучше инициализировать указатель на NULL, если по какой-либо причине вы не можете инициализировать его во время объявления . Например:
обычно функция может проверить значение указателя на NULL, чтобы убедиться, что указатель был инициализирован ранее. Если вы явно не установили значение NULL, и оно указывает на случайное значение, то оно может быть разыменовано, вызывая segfault.
Позволять программистам использовать неинициализированные переменные — большая ошибка со стороны разработчиков языка. Например, это может привести к значению undefined в JavaScript, которое чревато сопутствующими ошибками.
Такую оплошность легко совершить и тяжело отследить. Особенно при выполнении программы на разных платформах. И необходимости в этой особенности нет — переменная всегда должна иметь определенное значение.
Проблема
Локальные переменные, переменные-поля и т. д. представляют собой неинициализированные переменные, то есть в них будет записано ровно то, что было записано в отведенной под них памяти при объявлении. В C++ существуют различные правила для работы с неинициализированными переменными, инициализированными переменными и нуль-инициализированными переменными. Очень путанный механизм.
Учитывая частоту, с которой в коде появляются неинициализированные переменные, можно подумать, что отследить подобные ситуации в коде легко. Совсем нет. Да, конечно же, большая часть автоматически инициализируется нулем, если не указано иное. Однако так происходит не всегда. Например, в результате выполнения этого кода:
В результате выполнения этого кода у автора статьи всегда печатается False и 0 . Ошибок, связанных с утечкой памяти, можно избежать, используя valgrind .
Белкасофт , Санкт-Петербург, можно удалённо , От 120 000 до 190 000 ₽
Но основная проблема заключается в том, что программы даже в таком случае продолжают работать, что снижает вероятность обнаружения ошибки. Обычно ее можно отследить, только лишь запустив тестирование на другой платформе.
Почему ноль?
Почему программа автоматически инициализирует переменную нулем? На самом деле, это делает не программа, а операционная система, которая просто не позволит приложению проникнуть в неинициализированную область памяти, такова природа этого защитного механизма. Если программа A отработала свое, и результаты ее работы остались где-то в памяти, то программа B не должна обнаружить их во время своей работы, а потому ядро самостоятельно очищает память. В частности, Linux прописывает в освободившуюся память нули.
Естественно, нет никакого правила, чем заполнять память. Вероятно, OpenBSD делает это как-то иначе. Иначе чистит память и ArchLinux, запущенный в VirtualBox. Этим может заниматься не только операционная система — то же может проделать и другая программа, например. И если вдруг в область памяти, которую использует приложение, попадут какие-нибудь значения, изменить их сможет уже только сама эта программа.
Любопытно, что это стало одной из причин появления Heartbleed бага.
Решение
Язык просто не должен позволять использовать неинициализированные переменные. Необязательно нужно указывать конкретное значение — значение просто обязательно должно быть. Например, значением по умолчанию может стать все тот же ноль. Вне зависимости от того, как и в какой области видимости я создал данную переменную.
В то же время, могут быть сделаны определенные исключения в пользу оптимизации. Например, при работе с памятью на низком уровне. Впрочем, оптимизатор обычно обнаруживает неиспользуемые переменные и может их принудительно не инициализировать. Если нам нужен блок неинициализированной памяти, у нас должна быть возможно выделить ее самостоятельно. В этом случае программист четко отдает себе отчет в производимых им действиях, а потому не должен попасть в ловушку.
И чтобы полностью отследить все моменты с инициализацией памяти, язык также должен иметь специальное значение noinit , которое будет показывать, что данная переменная не нуждается в инициализации.
Автор статьи уверен, что уже в ближайшем стандарте C++ должны быть реализованы эти изменения. Превращение неинициализированных ранее переменных в инициализированные не повлияет на корректность выполнения ни одной программы. Такое нововведение будет полностью backwards compatible, и серьезно улучшит популярный язык.
В отличие от некоторых языков программирования, C/C++ не инициализирует большинство переменных автоматически заданным значением (например, нулем). Таким образом, когда компилятор выделяет переменной место в памяти, значением по умолчанию для этой переменной является любое (мусорное) значение, которое уже находится в этой области памяти! Переменная, которой не было присвоено известное значение (обычно посредством инициализации или присваивания), называется неинициализированной переменной.
Примечание автора
- инициализация = объекту присваивается известное значение в точке определения;
- присваивание = объекту присваивается известное значение в точке, выходящей за рамки определения;
- неинициализированный = объекту еще не присвоено известное значение.
В качестве отступления.
Отсутствие инициализации является оптимизацией производительности, унаследованной от C, когда компьютеры были медленными. Представьте себе случай, когда вы собираетесь прочитать 100 000 значений из файла. В таком случае вы можете создать 100 000 переменных, а затем заполнить их данными из файла.
Если бы C++ инициализировал все эти переменные при создании значениями по умолчанию, это привело бы к 100 000 инициализаций (что было бы медленно) и к небольшой выгоде (поскольку вы всё равно перезапишете эти значения).
На данный момент вы всегда должны инициализировать свои переменные, потому что затраты на это ничтожны по сравнению с выгодой. Как только вы освоите язык, тогда могут быть определенные случаи, когда вы можете пропустить инициализацию в целях оптимизации. Но делать это всегда нужно выборочно и намеренно.
Использование значений неинициализированных переменных может привести к неожиданным результатам. Рассмотрим следующую короткую программу:
В этом случае компьютер выделит для x некоторую неиспользуемую память. Затем он отправит значение, находящееся в этой ячейке памяти, в std::cout , который напечатает значение (интерпретируемое как целое число). Но какое значение он напечатает? Ответ – «кто знает!», и ответ может (или не может) меняться каждый раз, когда вы запускаете программу. Когда автор запускал эту программу в Visual Studio, std::cout в первый раз вывел значение 7177728, а во второй раз – 5277592. Не стесняйтесь компилировать и запускать программу самостоятельно (ваш компьютер не взорвется).
В качестве отступления.
Некоторые компиляторы, такие как Visual Studio, при использовании конфигурации отладочной сборки будут инициализировать содержимое памяти некоторым предустановленным значением. Этого не произойдет при использовании конфигурации сборки выпуска. Поэтому, если вы хотите запустить указанную выше программу самостоятельно, убедитесь, что вы используете конфигурацию сборки выпуска (чтобы вспомнить, как это сделать, смотрите урок «0.9 – Настройка компилятора: конфигурации сборки»). Например, если вы запустите приведенную выше программу в конфигурации отладки в Visual Studio, она будет неизменно печатать -858993460 , потому что с помощью этого значения (интерпретируемого как целое число) Visual Studio инициализирует память в конфигурациях отладки.
Большинство современных компиляторов пытаются определить, используется ли переменная без присваивания значения. Если они смогут это обнаружить, они обычно выдадут ошибку времени компиляции. Например, компиляция приведенной выше программы в Visual Studio выдала следующее предупреждение:
Если ваш компилятор по этой причине не позволяет вам скомпилировать и запустить приведенную выше программу, вот возможное решение этой проблемы:
Использование неинициализированных переменных – одна из наиболее распространенных ошибок, которые совершают начинающие программисты, и, к сожалению, она также может быть одной из самых сложных для отладки (потому что программа всё равно может работать нормально, если неинициализированное значение было присвоено определенной области памяти, которая содержала приемлемое значение, например, 0).
Это основная причина использования оптимальной практики «всегда инициализировать переменные».
Неопределенное поведение
Использование значения из неинициализированной переменной – наш первый пример неопределенного поведения. Неопределенное поведение – это результат выполнения кода, поведение которого не определено языком C++. В этом случае в языке C++ нет правил, определяющих, что произойдет, если вы используете значение переменной, которой не было присвоено известное значение. Следовательно, если вы действительно сделаете это, результатом будет неопределенное поведение.
Код, реализующий неопределенное поведение, может проявлять любые из следующих симптомов:
- ваша программа при каждом запуске дает разные результаты;
- ваша программа постоянно дает один и тот же неверный результат;
- ваша программа ведет себя непоследовательно (иногда дает правильный результат, иногда нет);
- кажется, что ваша программа работает, но позже выдает неверные результаты;
- ваша программа вылетает сразу после запуска или позже;
- ваша программа работает с одними компиляторами, но не работает с другими;
- ваша программа работает до тех пор, пока вы не измените какой-нибудь другой, казалось бы, несвязанный код.
Или ваш код в любом случае может действительно вести себя правильно. Природа неопределенного поведения заключается в том, что вы никогда не знаете точно, что получите, будете ли вы получать это каждый раз, и изменится ли это поведение, когда вы внесете какие-либо изменения.
C++ содержит множество случаев, которые могут привести к неопределенному поведению, если вы не будете осторожны. Мы будем указывать на них в будущих уроках всякий раз, когда с ними столкнемся. Обратите внимание на эти случаи и убедитесь, что вы их избегаете.
Правило
Старайтесь избегать всех ситуаций, которые приводят к неопределенному поведению, например, использование неинициализированных переменных.
Примечание автора
Один из наиболее распространенных типов комментариев, которые мы получаем от читателей, гласит: «Вы сказали, что я не могу делать X, но я всё равно сделал это, и моя программа работает! Почему?".
Есть два общих ответа. Наиболее распространенный ответ заключается в том, что ваша программа на самом деле демонстрирует неопределенное поведение, но это неопределенное поведение в любом случае дает желаемый результат… пока. Завтра (или на другом компиляторе или машине) этого может и не быть.
В качестве альтернативы, иногда авторы компиляторов допускают вольность к требованиям языка, когда эти требования могут быть более строгими, чем необходимо. Например, в стандарте может быть сказано: «Вы должны сделать X перед Y», но автор компилятора может счесть это ненужным и заставить Y работать, даже если вы сначала не выполните X. Это не должно влиять на работу правильно написанных программ, но в любом случае может привести к тому, что неправильно написанные программы будут работать. Таким образом, альтернативный ответ на вышеупомянутый вопрос заключается в том, что ваш компилятор может просто не следовать стандарту! Такое случается. Вы можете избежать этого, если отключили расширения компилятора, как описано в уроке «0.10 – Настройка компилятора: расширения компилятора».
Небольшой тест
Вопрос 1
Что такое неинициализированная переменная? Почему вам следует избегать их использования?
Неинициализированная переменная – это переменная, которой программа не присвоила значение (обычно посредством инициализации или присваивания). Использование значения, хранящегося в неинициализированной переменной, приведет к неопределенному поведению.
Вопрос 2
Что такое неопределенное поведение и что может произойти, если вы сделаете что-то, что демонстрирует неопределенное поведение?
Неопределенное поведение – это результат выполнения кода, поведение которого не определяется языком. Результатом может быть что угодно, в том числе и то, что ведет себя правильно.
Поиск ошибок работы с памятью в C/C++ при помощи Valgrind
Простой пример
Перейдем сразу к делу и проверим работу Valgrind на такой программе:
Компилируем с отладочными символами и запускаем ее под Valgrind:
==1948== HEAP SUMMARY:==1948== in use at exit: 10,240 bytes in 10 blocks
==1948== total heap usage: 11 allocs, 1 frees, 11,264 bytes allo.
==1948==
==1948== LEAK SUMMARY:
==1948== definitely lost: 10,240 bytes in 10 blocks
==1948== indirectly lost: 0 bytes in 0 blocks
==1948== possibly lost: 0 bytes in 0 blocks
==1948== still reachable: 0 bytes in 0 blocks
==1948== suppressed: 0 bytes in 0 blocks
==1948== Rerun with --leak-check=full to see details of leaked memory
Видим, что память утекла. Запускаем с --leak-check=full :
==2047== 10,240 bytes in 10 blocks are definitely lost in loss recor.==2047== at 0x4C2AF1F: malloc (in /usr/lib/valgrind/vgpreload_mem.
==2047== by 0x400561: run_test (vgcheck.c:8)
==2047== by 0x4005AF: main (vgcheck.c:18)
Теперь раскомментируем вызов free и уберем инициализацию переменной delta . Посмотрим, увидит ли Valgrind обращение к неинициализированной памяти:
==2102== Conditional jump or move depends on uninitialised value(s)==2102== at 0x4E8003C: vfprintf (in /usr/lib/libc-2.25.so)
==2102== by 0x4E87EA5: printf (in /usr/lib/libc-2.25.so)
==2102== by 0x4005CA: run_test (vgcheck.c:10)
==2102== by 0x4005F4: main (vgcheck.c:18)
Видит. Запустим с --track-origins=yes чтобы найти, откуда именно пришла неинициализированная переменаая:
==2205== Conditional jump or move depends on uninitialised value(s)==2205== at 0x4E800EE: vfprintf (in /usr/lib/libc-2.25.so)
==2205== by 0x4E87EA5: printf (in /usr/lib/libc-2.25.so)
==2205== by 0x4005CA: run_test (vgcheck.c:10)
==2205== by 0x4005F4: main (vgcheck.c:18)
==2205== Uninitialised value was created by a stack allocation
==2205== at 0x400586: run_test (vgcheck.c:6)
Как видите, Valgrind нашел место объявления неинициализированной переменой с точностью до имени файла и номера строчки.
Теперь исправим все ошибки:
==2239== HEAP SUMMARY:==2239== in use at exit: 0 bytes in 0 blocks
==2239== total heap usage: 11 allocs, 11 frees, 11,264 bytes allo.
==2239==
==2239== All heap blocks were freed -- no leaks are possible
Ну разве не красота?
valgrind --leak-check =no --track-origins = yes --gen-suppressions =all \--read-var-info = yes \
--log-file = $HOME / work / postgrespro / postgresql-valgrind /% p.log \
--suppressions =src / tools / valgrind.supp --time-stamp = yes \
--trace-children = yes postgres -D \
$HOME / work / postgrespro / postgresql-install / data-master \
2 >& 1 | tee $HOME / work / postgrespro / postgresql-valgrind / postmaster.log
Полный пример вы найдете в файле valgrind.sh из этого репозитория на GitHub.
Еще стоит отметить флаг --suppressions , который задает файл с описанием ошибок, которые следует игнорировать, а также флаг --gen-suppressions=all , который в случае возникновения ошибок генерирует строки, которые можно добавить в этот самый файл для игнорирования ошибок. Кстати, в файле можно использовать wildcards, в стиле:
Использование Valgrind совместно с GDB
Эти флаги говорят Valgrind остановить процесс и запустить gdb-сервер после возникновения первой ошибки. Можно указать и --vgdb-error=0 , чтобы подключиться к процессу отладчиком сразу после его запуска. Однако это может быть плохой идеей, если вы также указали --trace-children=yes и при этом программа создает множество дочерних процессов.
При возникновении ошибки Valgrind напишет:
==00:00:00:06.603 16153== TO DEBUG THIS PROCESS USING GDB: start GDB.==00:00:00:06.603 16153== /path/to/gdb postgres
==00:00:00:06.603 16153== and then give GDB the following command
==00:00:00:06.603 16153== target remote | vgdb --pid=16153
После этого, чтобы подключиться к процессу при помощи GDB, говорим:
Из интересных дополнительных команд доступны следующие. Посмотреть список утечек:
Узнать, кто ссылается на память:
Дальше отлаживаем, как обычно. Например, говорим continue . Как только произойдет следующая ошибка, программа снова остановится по брейкпоинту. Можно смотреть значения переменных, перемещаться между фреймами стека, ставить собственные брейкпоинты, и так далее.
Заключение
К сожалению, в рамках одного поста невозможно рассмотреть абсолютно все возможности Valgrind. Например, в него входят инструменты Callgrind и Massif, предназначенные для поиска узких мест в коде и профилирования памяти соответственно. Эти инструменты я не рассматриваю, так как для решения названных задач предпочитаю использовать perf и Heaptrack. Также существует инструмент Helgrind, предназначенный для поиска гонок. Его изучение я вынужден оставить вам в качестве упражнения.
Как видите, пользоваться Valgrind крайне просто. Он, конечно, не идеален. Как уже отмечалось, Valgrind существенно замедляет выполнение программы. Кроме того, в нем случаются ложноположительные срабатывания. Однако последняя проблема решается составлением специфичного для вашего проекта файла подавления конкретных отчетов об ошибках. Так или иначе, если вы пишете на C/C++ и не прогоняете код под Valgrind хотя бы в Jenkins или TeamCity незадолго до релиза, вы явно делаете что-то не так!
Как я могу реализовать эту структуру данных, не вызывая неопределенного поведения и не сталкиваясь с такими инструментами, как Valgrand или ASAN?
Решение
Я вижу четыре основных подхода, которые вы можете использовать. Они применимы не только к C ++, но и к большинству других языков низкого уровня, таких как C, которые делают возможным неинициализированный доступ, но не позволил, и последнее применимо даже к «безопасным» языкам более высокого уровня.
Так что в любом случае вы просто реализуете его, зная, что большинство или все текущие компиляторы просто скомпилируют его в ожидаемый код и знают, что ваш код не соответствует стандартам.
По крайней мере в мой тест все gcc , clang а также icc не воспользовался незаконным доступом, чтобы сделать что-нибудь сумасшедшее. Конечно, тест не является исчерпывающим, и даже если вы его построите, поведение может измениться в новой версии компилятора.
Тем не менее, этот подход теоретически небезопасный и вы должны очень тщательно проверить скомпилированный вывод и иметь дополнительные меры предосторожности, если вы его принимаете.
Если вы выберете такой подход, инструменты, такие как valgrind скорее всего, сообщит об ошибке неинициализированного чтения.
Поскольку он работает на основе трассировки стека, вы, вероятно, столкнетесь с трудностями, если чтение будет происходить во встроенном коде, поскольку верхняя часть стека будет отличаться для каждого сайта вызовов. Вы могли бы избежать этого, убедившись, что функция не встроена.
То, что плохо определено в стандарте, обычно четко определено на уровне сборки. Вот почему компилятор и стандартная библиотека часто могут реализовывать вещи быстрее, чем вы могли бы достичь с помощью C или C ++: libc подпрограмма, написанная на ассемблере, уже нацелена на конкретную архитектуру и не должна беспокоиться о различных предостережениях в спецификации языка, которые призваны ускорить работу на различном оборудовании.
Если вы используете calloc 2 , Вы явно запрашиваете обнуленную память у основного распределителя. Сейчас правильный версия calloc может просто позвонить malloc и затем обнуление возвращенной памяти, но фактические реализации полагаются на тот факт, что процедуры выделения памяти на уровне ОС ( sbrk а также mmap (в значительной степени) обычно возвращает вам обнуленную память в любой ОС с защищенной памятью (то есть со всеми большими), чтобы избежать обнуления памяти снова.
С практической точки зрения, для больших распределений это обычно выполняется путем реализации вызова, подобного анонимному. mmap составив карту специального нулевая страница всех нулей. Когда (если когда-либо) память записывается, действительно ли копирование при записи выделяет новую страницу. Таким образом, выделение больших обнуленных областей памяти может быть бесплатно поскольку ОС уже нужно обнулить страницы.
В этом случае реализация вашего разреженного набора поверх calloc может быть такой же быстрой, как и номинально неинициализированная версия, при этом будучи безопасной и соответствующей стандартам.
Calloc Предостережения
Вы должны, конечно, проверить, чтобы убедиться, что calloc ведет себя как ожидалось. Оптимизированное поведение обычно происходит только тогда, когда ваша программа инициализирует много долгоживущей обнуленной памяти, приблизительно «заранее». То есть типичная логика для оптимизированного calloc, если что-то вроде этого:
В основном, malloc инфраструктура (которая также лежит в основе new and friends) имеет (возможно, пустой) пул памяти, который он уже запросил у ОС и обычно сначала пытается выделить его там. Этот пул состоит из памяти из последнего запроса блока от ОС, но не раздается (например, потому что пользователь запросил 32 байта, но выделенные запросы запрашивают фрагменты из ОС в блоках по 1 МБ, поэтому остается много), а также памяти, которая была передана процессу, но впоследствии возвращена через free или же delete или что угодно. Память в этом пуле имеет произвольные значения, и если calloc Вы можете быть удовлетворены из этого пула, вы не получите свою магию, так как должен произойти нулевой инициатор.
С другой стороны, если память должна быть выделена из ОС, вы получаете волшебство. Так что это зависит от вашего варианта использования: если вы часто создаете и уничтожаете sparse_set объекты, вы, как правило, просто будете рисовать из внутреннего malloc бассейны и оплатит обнуление затрат. Если у вас долгоживущий sparse_set объекты, которые занимают много памяти, они, вероятно, были выделены при запросе ОС, и вы получили обнуление почти бесплатно.
Хорошей новостью является то, что если вы не хотите полагаться на calloc поведение выше (действительно, в вашей ОС или с вашим распределителем это может даже не быть оптимизировано таким образом), вы обычно можете повторить поведение, отображая в /dev/zero вручную для ваших ассигнований. В операционных системах, которые его предлагают, это гарантирует, что вы получите «дешевое» поведение.
Для решения, полностью независимого от платформы, вы можете просто использовать еще один массив, который отслеживает состояние инициализации массива.
Сначала вы выбираете какую-то гранулу, при которой вы будете отслеживать инициализацию, и используете битовую карту, где каждый бит отслеживает состояние инициализации этой гранулы sparse массив.
Например, допустим, вы выбрали гранулу размером 4 элемента, а размер элементов в вашем массиве составляет 4 байта (например, int32_t значения): вам нужно 1 бит, чтобы отслеживать каждые 4 элемента * 4 байта / элемент * 8 бит / байт, что составляет служебную нагрузку менее 1% 3 в выделенной памяти.
Теперь вы просто проверяете соответствующий бит в этом массиве перед доступом sparse , Это добавляет небольшую стоимость доступа к sparse массив, но не меняет общую сложность, и проверка все еще довольно быстро.
Например, ваш is_member функционировать сейчас похоже :
Сгенерированная сборка на x86 (gcc) теперь начинается с:
Это все связано с проверкой растровых изображений. Это все будет довольно быстро (и часто не по критическому пути, поскольку не является частью потока данных).
1% для значений примера).
Действительно ленивое решение
Стоит отметить, что есть сходство между calloc а также ленивый иници решения: оба лениво инициализируют блоки памяти по мере необходимости, но calloc решение отслеживает это неявно в аппаратном обеспечении через магию MMU с таблицами страниц и записями TLB, в то время как ленивый иници Решение делает это в программном обеспечении, с помощью растрового изображения, явно отслеживающего, какие гранулы были выделены.
Преимущество аппаратного подхода заключается в том, что он почти свободен (для случая «попадания», во всяком случае), поскольку он использует всегда присутствующую поддержку виртуальной памяти в ЦП для обнаружения пропусков, но преимущество программного обеспечения состоит в том, что он переносим и позволяет точный контроль размера гранул и т. д.
Вы можете на самом деле объединить эти подходы, чтобы создать ленивый подход, который не использует растровое изображение и даже не нуждается в dense массив вообще: просто выделите sparse массив с mmap как PROT_NONE так что вы ошибаетесь, когда читаете с нераспределенной страницы в sparse массив. Вы ловите ошибку и размещаете страницу в sparse массив со значением часового, указывающим «не присутствует» для каждого элемента.
Это самый быстрый вариант для «горячего» случая: вам не нужно . && dense[sparse[i]] == i проверяет больше.
- Ваш код на самом деле не переносим, так как вам нужно реализовать логику обработки ошибок, которая обычно зависит от платформы.
- Вы не можете контролировать размер гранулы: она должна быть с гранулярностью страницы (или несколькими кратными). Если ваш набор очень разреженный (скажем, менее 1 из 4096 занятых элементов) и распределен равномерно, вы в конечном итоге платите высокую стоимость инициализации, поскольку вам необходимо обработать ошибку и инициализировать полную страницу значений для каждого элемента.
- Промахи (т. Е. Доступ без вставки для установки несуществующих элементов) либо должны выделять страницу, даже если в этом диапазоне не будет элементов, либо каждый раз будет очень медленным (вызывая ошибку).
2 Действительно, единственное требование, чтобы вы использовали что-то, что вызывает calloc под прикрытием или выполняет эквивалентную оптимизацию с нулевым заполнением, но на основе моих тестов больше идиоматических C ++ подходов, таких как new int[size]() просто сделайте распределение с последующим memset , gcc делает оптимизировать malloc с последующим memset в calloc , но это бесполезно, если вы все равно пытаетесь избежать использования подпрограмм C!
3 Точно, вам нужно 1 дополнительный бит для отслеживания каждых 128 бит sparse массив.
Другие решения
Если мы перефразируем ваш вопрос:
Какой код читает из неинициализированной памяти без инструментов отключения, предназначенных для захвата операций чтения из неинициализированной памяти?
Если valgrind по-прежнему жалуется, но ваш алгоритм корректен даже при использовании этих неинициализированных данных, тогда вы можете использовать клиентские запросы для объявления этой памяти как инициализированной.
Читайте также: