Онлайн ACM подобные тестирующие системы

#linux #память #время #memory

                    
Я прочитал данную статью про лимиты памяти, и написал некий код, который вычисляет
те или иные значения памяти и времени.


Как я понял, функция clock() измеряет время процессора, которое сильно отличается
от того, что выводит мне команда time в шелле. Каким образом в тестирующих системах
это отслеживается?
Есть куча разных полей типа:

VmPeak:    11884 kB
VmSize:    11884 kB
VmLck:         0 kB
VmHWM:      1108 kB
VmRSS:      1108 kB
VmData:      272 kB
VmStk:        88 kB
VmExe:        16 kB
VmLib:      3244 kB
VmPTE:        48 kB
VmSwap:        0 kB


Как именно ограничивают ресурсы в тестирующих системах?
Вариант с ps aux совсем не годен для коротко работающих программ.

    

Ответы

Ответ 1

Обычно измеряется процессорное время. Это то, что time выводит как user.

По памяти - вам нужен показатель VmSize. Или VmPeak - это пиковое значение VmSize.
Если хотите считать совсем честно - то надо отнять от него data/stack/exe/lib - это
не "использование памяти" в смысле явного выделения в коде.

Данные по памяти нельзя определить после завершения процесса, так что единственный
вариант - достаточно часто опрашивать данные в фоне. Значение VmPeak за долю секунды
до завершения кода будет практически актуальным как "максимум использованной памяти".
И заодно следить за превышением выделенного времени выполнения.

Писать свою систему с нуля достаточно тяжело. Посмотрите исходники существующих систем,
например ejudge.


Ответ 2

ограничить время выполнения какой-нибудь программы можно, например, так:

$ программа & sleep 0.5; kill $! &>/dev/null && \
    echo "программа не уложилась в пол-секунды".


пример — «уложилась»:

$ sleep 0.4 & sleep 0.5; kill $! &>/dev/null && \
    echo "программа не уложилась в пол-секунды"
[1] 31136
[1]+  Done                    sleep 0.4


пример — «не уложилась»:

$ sleep 0.6 & sleep 0.5; kill $! &>/dev/null && \
    echo "программа не уложилась в пол-секунды"
[1] 31139
программа не уложилась в пол-секунды
[1]+  Terminated              sleep 0.6

Гибридное управление памятью

#память #любой_язык #сборщик_мусора

                    
В каком языке программирования можно комбинировать ручное управление памятью (в нужный
момент освободить, работа с указателями и так далее) и автоматическое, с достаточно
продвинутым сборщиком мусора по поколениям?

Иными словами, нужны две отдельные кучи для работы с памятью. 
    

Ответы

Ответ 1

Скорее всего вам подойдёт C++/CLI. Это Microsoft'овский гибрид C++ и платформы .NET.

В нём .NET-объекты создаются при помощи gcnew и управляются сборщиком мусора, а стандартные
C++-объекты создаются при помощи new и удаляются вручную через delete.

Оптимизация работы с памятью в С++

#cpp #память

решил написать свой .obj парсер, и столкнулся с небольшой проблемой...

...

std::vector> vertices;

std::string line;
std::ifstream inputStream(objFileName);
while (std::getline(inputStream, line))
{
    if (line.substr(0, 2) == "v ")
    {
        std::istringstream stream(line.substr(2));
        float x, y, z;
        stream >> x;
        stream >> y;
        stream >> z;
        vertices.push_back({ x, y, z, 1.0f });
    }

    ... // Texture coordinate, normals e.t.c.
}


Вопрос заключается в следующем, можно ли как-то оптимизировать в данном случае работу
с памятью, но так сказать не во вред удобности? При substr постоянно же будет аллоцироваться
новая строка, да и при создании стрима. Хотелось бы как-то ограничиться парой выделений
памяти и все на этом, а не фрагментировать кучу такими маленькими выделениями(вектор
в дальнейшем будет заменен, так как тоже очень затратно будет происходить реаллоцирование
памяти, пока просто хотел бы разобраться со строками)... 
    

Ответы

Ответ 1

В современном С++ всю работу с константными/немодифиуируемыми [под]строками имеет
смысл переводить на использование std::string_view. То есть везде, где в вашей программе
явно или концептуально выступает const std::string & он должен быть заменен на const
std::string_view &. Это относится и к вашему применению substr. Нет никаких причин
формировать целый новый std::string объект только ради выделения немодифицируемой подстроки.

По уму и std::string::substr должен был бы возвращать std::string_view, а не std::string,
но так исторически сложилось и сейчас уже не переделать.

В данном случае можно предложить заменить все

line.substr(i, j) 


на

std::string_view(line).substr(i, j)


Это избавит вас от ненужных промежуточных std::string объектов и сопутствующего выделения
памяти. 

Или уже с самого начала вы могли после получения line сразу сформировать

std::string_view line_view = line;


и дальше работать исключительно с line_view.

Это, однако, не избавит вас от выделения памяти при инициализации std::istringstream
и внутри std::istringstream. Здесь бы бы полезен парсер для std::string_view, но готового
в стандартной библиотеке нет (кроме sscanf). Сама стандартная библиотека еще толком
не перешла на использование std::string_view.



Ваше

vertices.push_back({ x, y, z, 1.0f });


это тоже потенциально - ненужное копирование. Возможно, что лучше

vertices.emplace_back(x, y, z, 1.0);


но это уже зависит от свойств Math::Vector4.

Как выделить память для большого двумерного массива в Си?

#c #массивы #память

Я работаю с большим двумерным массивом.
В случае, когда он размером 30 x 200, все считается. При больших объемах программа
вылетает... Мне посоветовали использовать memset(), но что-то не особо помогает...
Может быть у вас есть какие идеи?
#include 
#include 
#include 
#include 

double **B;

int main (int argc, char *argv[])
{ 
    int N, n_A;

    N = 32;
    n_A = 350; /* если сделать n_A = 200, то все работает */
    B = (double **)malloc(N * sizeof(double *));

    for(i = 0; i < N; i++)
    {
        B[i] = (double *)malloc(n_A * sizeof(double));
        memset(B[i], 0, n_A * sizeof(double));
    }

    free(B);

    return 0;
}
    

Ответы

Ответ 1

В целом код правильный, но нужно добавить проверку при выделении памяти: это необходимо,
потому что памяти может просто не хватать, и в этом случае программа будет падать,
потому что будет происходить запись в несуществующую память. То есть всякий раз, когда
происходит вызов malloc, необходимо проверить, что возвращаемое значение не равно NULL.
B = (double **)malloc(N * sizeof(double *));

/* Проверить, что память выделена */
if (B != NULL)
{
    for(i = 0; i < N; i++)
    {
        B[i] = (double *)malloc(n_A * sizeof(double));

        /* Проверить, что память выделена */
        if (B[i] != NULL)
        {
            memset(B[i], 0, n_A * sizeof(double));
            free(B[i]);
        }
    }

    free(B);
}

Кроме того, нужно не забывать освобождать память, выделяемую malloc внутри цикла,
иначе будут утечки.


Ответ 2

Вот это все можно сделать одной строкой 
double * B;
B = (double *) calloc (N * n_A, sizeof(double));
free (B);

Вместо вызова кучи функций вы вызываете одну, которая сразу выделяет память под весь
массив данных и обнуляет ее. 
Доступ к данным осуществляется по формуле
double a;
a = *(B + i * n_A + j);

где i - номер  строки, j - номер столбца


Ответ 3

При больших объемах программа вылетает...

Локальный буфер(точнее размер стекового фрейма) не должен иметь размер больший одной
страницы. Иначе произойдёт обращение за пределы сторожевой страницы стека, расширен
он не будет и возникнет исключение.

Функция memset_word делает пропуск между словами

#c #указатели #память #memory

Пока писал учебную ОС, пришлось в качестве одной из функций стандартной библиотеки
написать функцию memset_word. Проблема была тут же решена "в лоб":

    void memset_word(uint16_t* mem, uint16_t value, size_t count) {
        uint16_t* addr;
        for(addr = mem; addr < mem + count * sizeof(uint16_t);
                addr += sizeof(uint16_t)) {
            *addr = value;
        }
    }


Но у этой функции было обнаружено неприятное свойство: она записывает слова через
одно. Другими словами, память была такая:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00,

а после вызова

    memset((uint16_t*) 0, 0xCDAB, 3)


стала такая:

AB CD 00 00 AB CD 00 00 AB CD 00 00 00 00 00 00 00 00 00 00,

хотя должна была стать такой:

AB CD AB CD AB CD 00 00 00 00 00 00 00 00 00 00 00 00 00 00.

В принципе, помогает замена addr += sizeof(uint16_t) на addr++, но я не понимаю:
ведь указатели в C - настоящие адреса, так почему же для того, чтобы перейти к следующему
слову, нужно прибавлять 1, а не размер слова? Или же ошибка кроется где-то в коде функции?
Прошу объяснить мне это.
    

Ответы

Ответ 1

У вас эта функция

   void memset_word(uint16_t* mem, uint16_t value, size_t count) {
        uint16_t* addr;
        for(addr = mem; addr < mem + count * sizeof(uint16_t);
                addr += sizeof(uint16_t)) {
            *addr = value;
        }
    }


некорректная. В ней неправильно используется арифметика указателей.

Я думаю, вы имели в виду следующее

   void memset_word(uint16_t* mem, uint16_t value, size_t count) {
        for(uint16_t *addr = mem; addr != mem + count; ++addr )
            *addr = value;
        }
    }


Вы должны перейти к следующему объекту. Увеличение указателя на 1 увеличивает его
адрес на sizeof( uint16_t ).

В этом состоит принцип работы оператора индексирования, когда вы пишите, например,

mem[1]


что эквивалентно выражению *(mem + 1) и в виду коммутативности операции сложения
вы можете также записать 

1[mem]


Ответ 2

Я бы сказал не так. Арифметика указателей верная, и Ваша функция работала бы правильно,
если бы архитектура машины была 16-разрядная. В 32-разрядных машинах размер слова равен
4 байтам. При этом все числа (кроме char), размер которых меньше 4 байт, аппаратно
выравниваются по 4-байтному слову. Другими словами, нельзя (не рекомендуется) разместить
два 16-разрядных слова в одном 4-байтном аппаратном слове. 

В случае, если вы запишете подряд два 16-разрядных слова, процессору придётся осуществлять
больше операций, чтобы извлечь его из оперативной памяти и записать обратно. Нужно
извлечь 4 байта (1 инструкция), далее в зависимости от того, младшее это слово или
старшее (сравнение, условный переход - 2 инструкции) осуществляется наложение маски
0xFFFF0000 или 0x0000FFFF соответственно (2 инструкции). Если это старшее слово, то
осуществляется сдвиг на 16 бит (1 инструкция). Все эти инструкции осуществляются аппаратно.
Итого извлечение 16-разрядного полуслова из 32-разрядного слова тяжелее в 6 раз (приблизительно).
Поэтому решите, под какую архитектуру вы пишете и какой размер слова вам нужен.

Виртуальная память процесса в windows, что из неё видно и как меняются адреса?

#windows #память #pe

Вопрос по загрузке PE и распределению в адресов в режиме пользователя.
Насколько я знаю, PE-секции выгружаются в общую для всех пользовательских программ
область, в зависимости от доступности, и адреса задаются при загрузке в память, но
тут вопрос - как происходит адресация внутри программы, раз мы не меняя кода получаем
работоспособную программу и при этом можем через ту же память обращаться в адресное
пространство других процессов? К примеру, у меня в программе по адресу 0x1 лежит mov
ax,bx и когда происходит jmp 0x1 он перекидывает меня именно в мою программу, а не
в чужую, при этом я могу прочитать тот же 0x1 другой программы как?
И как бы мне выцепить user32 и kernel32 без таблицы импорта, но из своего pe-файла?
И чего там ещё интересного можно найти?
    

Ответы

Ответ 1

Насколько я знаю PE-секции выгружаются в общую для всех пользовательских программ
область в зависимости от доступности и адреса задаются при загрузке в память


Так было до Windows 3.1 включительно, когда виртуальной памяти попросту не существовало,
и разделение производилось по отовсюду доступным сегментам. В современных же операционных
системах каждый процесс находится в собственном, изолированном адресном пространстве
(«песочнице»).

Согласен, если файл (в том числе исполняемый) отображается в несколько процессов
в режиме только на чтение и без каких-либо изменений, то операционная система может
(но не обязана) сэкономить немного ОЗУ и отобразить соответствующие страницы виртуальной
памяти этих процессов в один и тот же регион памяти физической.

Однако это всего лишь трюк на уровне отображения виртуальной памяти на физическую
силами железа. С точки зрения самих программ никакого общего региона не существует.


  к примеру у меня в программе по адресу 0x1 лежит mov ax,bx и когда происходит jmp
0x1 он перекидывает меня именно в мою программу а не в чужую


Перед тем, как переключить выполнение на какой-либо поток вашего процесса, операционная
система производит определённую донастройку процессора. В частности, она извлекает
из своих внутренних структур физический адрес карты отображения памяти и передаёт его
специальному блоку процессора, мапперу.

Маппер же использует указанную карту примерно следующим образом:



(Иллюстрация взята из ответа на вопрос «Какую модель памяти сегментную или страничную
использует windows, linux, macos?»)


  при этом я могу прочитать тот же 0x1 другой программы как?


Надо попросить операционную систему не выделять пустую страницу, как она это обычно
делает, а создать привязку к уже существующей странице. Иными словами, как бы прорубить
окно в чужое адресное пространство.

Однако отображаемый блок не должен накладываться на уже занятый регион виртуальной
памяти вашего процесса. С другой стороны, это окно можно создать в любом месте памяти
вашей программы.

Для этого необходимо вызвать системную функцию MapViewOfFileEx(), указав целевой
процесс и адрес в его виртуальной памяти.


  И как бы мне выципить user32 и kernel32 без таблицы импорта но из своего pe-файла?


LoadLibrary() + GetProcAddress(). Всё остальное — хаки и ненадёжно.

проблемы с памятью

#c #указатели #память #динамические_массивы

Доброго времени суток! Приведу пример кода, в котором укажу лишь те места, где выделяется
непосредственно память. Заранее удалю все места, где я эту память освобождаю, чтобы
вы, как более опытные программисты в Си, чем я, начинающий, указали мне, как лучше
следует с ней обращаться, а главное - показали, из-за чего всё-таки у меня программа
в процессе выполнения вылетает с ошибкой .exe вызвал срабатывание точки останова.

Итак, сам код:

    void func(int *intArray, int mode, int length, int **p, int **hufTemp, 
    int *num)
    {
    int *intPtrTemp;
    int *intListTemp, *intListIndexes;
    int *intPtrLength, *intPtrLength_Temp;
    int *intPtrBlCount; 
    int *intPtrNextCode;
    int *intPtrHuffmanTree;
    int *intDictHuffmanTree;
    int count = 0 , max = 0;



    intPtrTemp = (int*)malloc(length * sizeof(int));
    memset(intPtrTemp, 0, length * sizeof(int));
    memcpy(intPtrTemp, intArray, length * sizeof(int));

    // процесс вычисления count
    intListTemp = (int*)malloc(count * sizeof(int));
    intListIndexes = (int*)malloc(count * sizeof(int));
    memset(intListTemp, 0, count * sizeof(int));
    memset(intListIndexes, 0, count * sizeof(int));

    intPtrLength = (int*)malloc(count * sizeof(int));
    memset(intPtrLength, 0, count * sizeof(int));
    memcpy(intPtrLength, intListTemp, count * sizeof(int));

    intPtrLength_Temp = (int*)malloc(count * sizeof(int));
    memset(intPtrLength_Temp, 0, count * sizeof(int));
    memcpy(intPtrLength_Temp, intPtrLength, count * sizeof(int));

    // процесс вычисления max
    memcpy(intPtrLength_Temp, intPtrLength, count * sizeof(int));
    intPtrBlCount = (int*)malloc((max + 1)*sizeof(int));
    memset(intPtrBlCount, 0, (max + 1) * sizeof(int));

    intPtrNextCode = (int*)malloc((max + 1) * sizeof(int));
    memset(intPtrNextCode, 0, (max + 1) * sizeof(int));

    intPtrHuffmanTree = (int*)malloc(count * sizeof(int));
    memset(intPtrHuffmanTree, 0, count * sizeof(int));

    intDictHuffmanTree = (int*)malloc(count * sizeof(int));
    memset(intDictHuffmanTree, 0, count * sizeof(int));

    memcpy(*p, intPtrLength, count * sizeof(int));
    memcpy(*hufTemp, intDictHuffmanTree, count * sizeof(int));

    *num = count;
}
void main()
{
    char **dictFirstHuffmanTree;
    int intHuffmanTree_Init[19];
    int *p, *_intHuffmanTree, count = 0;

    // вычисление элементов массива intHuffmantree_Init
    p = (int*)malloc(sizeof(int));
    _intHuffmanTree = (int*)malloc(sizeof(int));

    func(intHuffmanTree_Init, 1, 19, &p, &_intHuffmanTree, &count);
    dictFirstHuffmanTree = (char**)malloc(count * sizeof(char*));
    getchar();
}


Пара важных моментов.
1. Функция содержится в файле test1.c. Дёргаю я её из файла test2.c. 
2. Если всё писать в одном файле, вот так как я представил (т.е. без освобождения
памяти), то всё прекрасно работает.
    

Ответы

Ответ 1

Как минимум:

p = (int*)malloc(sizeof(int));


Теперь p указывает на блок в 4 байта (ну, чтоб не писать sizeof(int), пусть 32-разрядная
программа).

Передаете его в функцию. Значение p не меняется, теперь это *p - раз в функцию передан
адрес p. И в этот блок вы копируете незнамо сколько памяти:

memcpy(*p, intPtrLength, count * sizeof(int));


Если count больше 1, вы выходите за рамки выделенного блока и перезаписываете служебные
структуры менеджера памяти.

Я не говорю, что это единственная ошибка, но дальше я не смотрю - пока что нет смысла...

И вы как, ничего не освобождаете выделенного? Устраиваете себе утечку памяти?

Создание хранилища объектов

#c_sharp #память

Товарищи, встал перед такой проблемой:

Мне необходимо реализовать нечто вроде хранилища объектов, которое бы выдавало по
одному экземпляру указанного объекта на пользователя

Попробую пояснить с помощью псевдокода:

// Добавим в хранилище правило создания объекта 
storage.Add("tmp", () => new Foo()); 

{
    // В хранилище пока нет сгенерированных объектов
    // Так что создаётся новый, сохраняется и возвращается 
    Foo tmp0 = storage["tmp"];
}

// Здесь ссылка на tmp0 уже недействительна 
// Так что единственная ссылка на тот созданный объект лежит внутри хранилища 
// Возвращаем тот же объект, что был в tmp0
Foo tmp1 = storage["tmp"];

// Тот объект, что был создан для tmp0, а теперь хранится в tmp1, уже занят 
// Так что создаём новый объект, сохраняем его в хранилище и его же и возвращаем 
Foo tmp2 = storage["tmp"];


То есть при завершении области видимости для tmp0 хранилище, содержащее в себе ссылку
на тот же объект, его не удаляет, а сохраняет до следующего запроса подобного объекта. 

То есть логика такая:


Идёт запрос объекта по ключу 
Если в хранилище нет уже созданных объектов - сгенерировать его по заданному правилу,
сохранить и после этого вернуть . Иначе:
Проверить для каждого созданного объекта, есть ли на него ссылка в пользовательском
коде. Если нет (то есть единственная ссылка лежит в самом хранилище) - вернуть найдённый
объект 


Такое поведение нужно мне по следующей причине: создание Foo - трудоёмкий процесс.
Помимо этого Foo не является потокобезопасным, так что на руках у каждого пользователя
Foo должен быть свой уникальный экземпляр, который, возможно, уже был создан и использован
ранее. 

Вроде как нигде нет «счётчика» ссылок на объекты, так как сборщику мусора плевать,
сколько там раз была объявлена ссылка на определённый объект. Важно лишь то, есть ли
таковая ссылка вообще

Так что даже не знаю, возможно ли вообще реализовать подобное средствами C#...



UPD:

Я никак не могу выбрать, какой ответ пометить галочкой, ибо ответы от iluxa1810 и
default locale  являются более правильными для общего случая. Однако в рамках моей
весьма специфичной задачи более подходит метод, описанный в ответе от John... 
    

Ответы

Ответ 1

Можно вывернуться, создав класс-обертку.

Я постараюсь вкратце сейчас, потому что с телефона.

Суть в том, что мы используем финализатор обертки, чтобы отловить событие удаления
обертки и вернуть наш экземпляр в строй.

Создаём наш класс-обертку:

class FooWrapper
{
   public event Action Final;

   private Foo foo;
   private int id;

   public FooWrapper(Foo foo, int id)
   {
      this.foo = foo;
      this.id = id;
   }

   // Вот и наш финализатор
   ~FooWrapper()
   {
       if (Final != null)
           Final(id)
   }
}


В самой программе создаём два словаря. Один - для неиспользуемых экземпляров foo,
а второй - для используемых.

Думаю, логика более или менее понятна? 

1) по требованию пользователя ищется в словарях экземпляр Foo. В данном случае по Id.

2) если нет, то создаётся Foo и помещается во второй словарь. Его мы передаём в FooWrapper
и обязательно подписываемся на событие Final. Полученный FooWrapper уже отдаем пользователю.

3) после того, как у пользователя пропадают все ссылки на FooWrapper срабатывает
финализатор, в котором срабатывает событие Final, передающее ID нашего Foo.

4) В основной программе мы получаем этот Id и переносим из второго словаря в первый.

Главный недостаток, что в данном случае мы полностью исключает возможность взаимодействия
напрямую с foo, только через методы, который в fooWrapper пропишешь.


Ответ 2

Вот тут похожий вопрос и там предоставляется решение в виде использования WeakReference
-это такая ссылка на объект, которая не препятствует сборки мусора. У него есть свойство
IsAlive, которое говорит жив ли объект или уже был собран сборщиком мусора.
Мне видится, что это вы можете задействовать в своей задаче. В вашем случае, объект
будет жив до тех пор, пока кто-то на него ссылается из кода.

Проверить, есть ли ссылка на объект в коде нельзя. .NET ушли от подсчета кол-ва ссылок
на объект в пользу построения графа доступности объектов.

Как альтернативный вариант- это ввести внутри вашего хранилища подсчет, заставляя
пользователя вызывать спец. метод. Но тут все строится на доверии... Например, вдруг
забудут что-либо вызвать => объект будет зарегистрирован за кем-то.


Ответ 3

Возможно, в Net найдется механизм, который решит задачу, в том виде, в каком Вы ее
написали. Но, если честно, мне это решение кажется неочевидным и хрупким:


неочевидным, т.к. конец блока кода легко пропустить при чтении, и, поэтому, редко
используется для критичных операций:

} //за одним символом здесь кроется важная операция по освобождению объекта.


Как разработчик, я ожидаю, что блоки кода можно свободно переставлять при рефакторинге.
В данном случае при этом нужно будет очень внимательно отследить срок жизни всех переменных.
Ситуация усложнится если ссылки на Foo будут сохраняться в полях других классов (объекты
которых сами будут храниться в коллекциях и захватываться в лямбдах).
хрупким, т.к. в данном случае логика будет сильно зависеть от работы сборщика кода,
которую сложно контролировать.


Альтернатива: объектный пул

Для решения Вашей проблемы (дорогостоящие объекты, которые желательно переиспользовать)
подойдет шаблон проектирования «объектный пул». Пулы широко используются для схожих
задач (хранения соединений к БД, например).

В простейшем варианте Вам достаточно:


Реализовать для Foo интерфейс IDisposable.
В storage отслеживать вызов метода Dispose для созданных Foo и освобождать объекты.
В вызывающем коде всегда оборачивать полученные из storage объекты в блок using
Для чистоты эксперимента можно вынести методы/свойства Foo в отдельный интерфейс,
который и возвращать из storage. Реализацию Foo оставить доступной только для storage,
чтобы никто не мог переопределить методы.


Решение скучное и предполагает изменение вызывающего кода. Зато в данном варианте
процесс освобождения объектов становится очевидным.

Ну и код будет выглядеть примерно так:

 using(var tmp0 = fooPool.GetFoo("tmp")) 
 {
      //работаем с одним объектом
 }

 using(var tmp1 = fooPool.GetFoo("tmp")) 
 {
      using(var tmp2 = fooPool.GetFoo("tmp")) 
      {
           //работаем с двумя объектами
      }
 }

Структура сегментов в адресном пространстве процесса

#память #процесс

|----------------------------Kernel Space------------------------------|  0xFFFFFF
                                                                 
|                                                                      |
|                                                                      |
|                                                                      |
|↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓Stack↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓|
|                                                                      |
|                                                                      |
|                                                                      |
|↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓Memory mapping segment↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓|
|                                                                      |
|                                                                      |
|                                                                      |
|↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑Heap↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑|
|                                                                      |
|                                                                      |
|-----------------------------BSS  segment-----------------------------|
|-----------------------------Data segment-----------------------------|
|-----------------------------Text segment-----------------------------|
|                                                                      |
|---------------------------------OS-----------------------------------|
|________________________________BIOS__________________________________| 0x000000 


Вопросы:

1) Как устроен Memory mapping segment?

2) Есть ли сегмент для констант?

3) В С++ есть и Heap и Free Store, или Heap интерпретируется как Free Store (если
да, то как размещен?) ?

4) Есть сегменты(с показанных выше) которые могут отсутствовать?

5) Есть замечания к указанной структуре памяти?
    

Ответы

Ответ 1

Константы обычно размещаются в текстовом сегменте, т.к. он защищен от записи. 

В остальном картинка условно соответствует большинству реализаций с виртуальной памятью.
Также следует иметь в виду, что между показанными сегментами возможны "дыры" (в смысле
пространства виртуальных адресов). 

Распределение памяти для конкретных Linux программ на практике можно посмотреть в
файле /proc/{PID}/maps

В качестве примера, вот такая программка и результат ее выполнения:

avp@avp-ubu1:hashcode$ cat t-maps.c
#include 
#include 
#include 

static int data = 22;

int
main (int ac, char *av[])
{
  const char *p = "xaxa-xaxaxaxax";

  printf("main: %p  p: %p  &p: %p  &data: %p\n",
     main, p, &p, &data);
  char str[100];
  sprintf(str, "cat /proc/%d/maps", (int)getpid());
  system(str);
}
avp@avp-ubu1:hashcode$ g++ t-maps.c && ./a.out
main: 0x56352bf8278a  p: 0x56352bf828b8  &p: 0x7ffff853a718  &data: 0x56352c183010
56352bf82000-56352bf83000 r-xp 00000000 08:01 1179691                    /home/avp/hashcode/a.out
56352c182000-56352c183000 r--p 00000000 08:01 1179691                    /home/avp/hashcode/a.out
56352c183000-56352c184000 rw-p 00001000 08:01 1179691                    /home/avp/hashcode/a.out
56352ce80000-56352cea1000 rw-p 00000000 00:00 0                          [heap]
7fd21e33c000-7fd21e356000 r-xp 00000000 08:01 2159140                    /lib/x86_64-linux-gnu/libpthread-2.27.so
7fd21e356000-7fd21e555000 ---p 0001a000 08:01 2159140                    /lib/x86_64-linux-gnu/libpthread-2.27.so
7fd21e555000-7fd21e556000 r--p 00019000 08:01 2159140                    /lib/x86_64-linux-gnu/libpthread-2.27.so
7fd21e556000-7fd21e557000 rw-p 0001a000 08:01 2159140                    /lib/x86_64-linux-gnu/libpthread-2.27.so
7fd21e557000-7fd21e55b000 rw-p 00000000 00:00 0 
7fd21e55b000-7fd21e55e000 r-xp 00000000 08:01 2159128                    /lib/x86_64-linux-gnu/libdl-2.27.so
7fd21e55e000-7fd21e75d000 ---p 00003000 08:01 2159128                    /lib/x86_64-linux-gnu/libdl-2.27.so
7fd21e75d000-7fd21e75e000 r--p 00002000 08:01 2159128                    /lib/x86_64-linux-gnu/libdl-2.27.so
7fd21e75e000-7fd21e75f000 rw-p 00003000 08:01 2159128                    /lib/x86_64-linux-gnu/libdl-2.27.so
7fd21e75f000-7fd21e946000 r-xp 00000000 08:01 2159125                    /lib/x86_64-linux-gnu/libc-2.27.so
7fd21e946000-7fd21eb46000 ---p 001e7000 08:01 2159125                    /lib/x86_64-linux-gnu/libc-2.27.so
7fd21eb46000-7fd21eb4a000 r--p 001e7000 08:01 2159125                    /lib/x86_64-linux-gnu/libc-2.27.so
7fd21eb4a000-7fd21eb4c000 rw-p 001eb000 08:01 2159125                    /lib/x86_64-linux-gnu/libc-2.27.so
7fd21eb4c000-7fd21eb50000 rw-p 00000000 00:00 0 
7fd21eb50000-7fd21eb56000 r-xp 00000000 08:01 3670234                    /usr/lib/x86_64-linux-gnu/libgtk3-nocsd.so.0
7fd21eb56000-7fd21ed55000 ---p 00006000 08:01 3670234                    /usr/lib/x86_64-linux-gnu/libgtk3-nocsd.so.0
7fd21ed55000-7fd21ed56000 r--p 00005000 08:01 3670234                    /usr/lib/x86_64-linux-gnu/libgtk3-nocsd.so.0
7fd21ed56000-7fd21ed57000 rw-p 00006000 08:01 3670234                    /usr/lib/x86_64-linux-gnu/libgtk3-nocsd.so.0
7fd21ed57000-7fd21ed7e000 r-xp 00000000 08:01 2159121                    /lib/x86_64-linux-gnu/ld-2.27.so
7fd21ef5a000-7fd21ef5e000 rw-p 00000000 00:00 0 
7fd21ef7e000-7fd21ef7f000 r--p 00027000 08:01 2159121                    /lib/x86_64-linux-gnu/ld-2.27.so
7fd21ef7f000-7fd21ef80000 rw-p 00028000 08:01 2159121                    /lib/x86_64-linux-gnu/ld-2.27.so
7fd21ef80000-7fd21ef81000 rw-p 00000000 00:00 0 
7ffff851c000-7ffff853d000 rw-p 00000000 00:00 0                          [stack]
7ffff8563000-7ffff8566000 r--p 00000000 00:00 0                          [vvar]
7ffff8566000-7ffff8568000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
avp@avp-ubu1:hashcode$

Уровни кэша процессора

#память #кэширование

Возьмем пример:

L1 - 128Kb
L2 - 512Kb
L3 - 2Mb


Зачем нужно несколько уровней кэш памяти?

Почему скорость L1 > L2 > L3 (разный SRAM дизайн?)?

Зачем нужно L1i для инструкций и L1d для данных?

Как рассчитывается оптимальный размер и количество кэш уровней?
    

Ответы

Ответ 1

Зачем нужно несколько уровней кэш памяти?


Если бы могли, то весь кэш сделали бы L1. Да и вообще, все ОЗУ затащили бы в процессор
в виде кэша. Но тогда процессор будет много потреблять и расплавится (при заданной
технологии производства и допусках).


  Почему скорость L1 > L2 > L3 (разный SRAM дизайн?)?


Опять же чтобы процессор не расплавился.


  Зачем нужно L1i для инструкций и L1d для данных?


Теперь же две очереди, отдельно для инструкций, отдельно для данных. Вот и кэша два.


  Как рассчитывается оптимальный размер и количество кэш уровней?


Там ничего особо не рассчитывается. Сколько места на кристалле остается после размещения
ядер, все отдается под кэши разных уровней.

UPD1:

А вообще-то есть форумы разработчиков процессоров, даже русскоязычные (да-да не смейтесь).
На крайний случай есть форумы разработчиков плат, раньше это было на каких-нибудь телесистемах
а сейчас не знаю где, но можно найти. Спросите там, там Вам подробнее объяснят.


Ответ 2

Основная проблема в обеспечении максимальной загрузки процессора и минимизации простоев
из-за загрузки данных из памяти.

Несколько уровней кэша различаются скоростью доступа в первую очередь. Уровневое
кэширование позволяет оптимизировать загрузку данных из основной памяти и держать для
процессора нужные страницы "под рукой". 

Тут хорошая аналогия склад - магазин - холодильник - тарелка (кэширование продуктов). 

Подробно кэши описаны у Танненбаума (Архитектура ЭВМ).

Задачи с моделями памяти

#c #память

объясните пожалуйста, как решать такие задачи с моделями памяти:


  
  Установлена модель памяти COMPACT. Какой объем памяти будет занимать переменная
pd согласно описанию float *pd[5];?
  Установлена модель памяти MEDIUM. Какой объем памяти будет занимать переменная
a согласно описанию char *a[5][2];?
  Установлена модель памяти SMALL Имеется описание int a[10] = {1, 2, 3, 4, 5}, *p
= a+2; Какие из следующих выражений имеют значение 2?   
  
  
  (int)p - (int)a;  
  p - a  
  *p - *a;  
  (a[1] + *p) / 2
  
  

    

Ответы

Ответ 1

Вот тут приводят вот такую таблицу:



И дано такое пояснение: 


в колонке Code - указатели на функции;
в колонке Data - указатели на переменные;


Указатели near занимают 2 байта, указатели far - 4 байта.



Теперь, возвращаясь к вашим вопросам. Поскольку у вас нету указателей на функции,
то всегда смотрим в колонку Data:


Массив из 5-ти far указателей на float, т.е. 5 * 4 = 20 байт;
Двумерный массив из 10-ти near указателей на char, т.е. 10 * 2 = 20 байт;
Массив из 10 интов и один near указатель, но размерность указателя на ответ никак
не влияет. Правильные ответы: 2, 3, 4.

Виртуальная память против физической памяти

#память

Может кто-нибудь объяснить разницу между виртуальной памятью и физической памятью?
    

Ответы

Ответ 1

Физическая память - это память, реально находящаяся в оперативном запоминающем устройстве
компьютера. В ней размещаются код и данные всех запущенных на выполнение процессов.
У физической памяти есть определённые недостатки:


При запуске программы нужно гарантировать, что адреса, в которые она загружается,
не заняты другими процессами
Программа не может занимать физической памяти больше размера физической памяти
Нужно защищать участки памяти,занятые процессом, от несанкционированного доступа
других процессов


Для решения этих проблем существует аппарат виртуальной памяти. Каждая программа
выполняется в своём отдельном виртуальном адресном пространстве. Соответственно, программа
ничего не знает о том, в каких физических адресах она находится. А все работы по преобразованию
виртуальных адресов в физические берут на себя аппаратные средства компьютера. Как
правило, код и данные процесса реально загружаются в физическую память небольшими кусками
- страницами - когда они действительно нужны. Сама программа ничего об этих преобразованиях
не знает. Это позволяет


использовать в программе больше оперативной памяти, чем доступно на самом деле
избежать фрагментации памяти, т.к. страницы имеют небольшой фиксированный размер
и загружаются в свободной место
экономно использовать оперативную память


Ответ 2

Физическая память это оперативная память, которая находится на ОЗУ. Когда она заканчивается,
необходимо где-то хранить данные запущенных программ, поэтому на жёстком диске выделяется
место под виртуальную память, которая выступает в роли оперативной памяти.

Заполнение участков памяти реализуется непосредственно ОС.

Освобождение ресурсов, выделенных потоку

#c #память #unix #freebsd #pthread

Всем добрый день!
Хотелось бы обсудить следующую проблему : в программе средствами библиотеки pthread
создается поток, ОС выделяет ему некоторый обьем памяти на стек и т.п., после того,
как данный поток отработал и завершился, из другого потока вызывается pthread_join(),
забирающая код возврата. При этом, не заметно, чтобы память, выделенная для данного
потока, освобождалась (при вызове pthread_create() выделилось порядка 100 кб, из которых
ничего не освободилось ни после return(), ни после pthread_join()). Кто-нибудь может
пояснить, почему? Я что-то не так делаю, или это может быть обусловлено поведением ОС ?    

Ответы

Ответ 1

@margosh, я тоже (солидарно с @mikillskegg и почти интуитивно) считаю, что память,
которую брал поток, используется повторно. Иллюстрацию приведу прямо здесь.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fatal(msg) ({perror(msg); exit(-1);})

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int nth = 0;

void *
thcli (void *a)
{
  pthread_mutex_lock(&lock);
  nth--;
  pthread_mutex_unlock(&lock);

  return (void *)1;
}

int
main (int ac, char *av[])
{
  int i, n = av[1]? atoi(av[1]):100;
  if (n < 1)
    n = 100;
  pthread_t th[n];
  void *res[n];
  char buf[100];

  do {
    pthread_mutex_lock(&lock);
    for (i = 0; i < n; i++) {
      if (pthread_create (&th[i], NULL, thcli, NULL))
        fatal("create");
      nth++;
    }
    printf ("run %d nth = %d\n",i,nth);
    pthread_mutex_unlock(&lock);
    for (i = 0; i < n; i++) {
      if (pthread_join (th[i], &res[i]))
        fatal("join");
    }
    printf ("join %d nth = %d\nAgain ?\n",i,nth);
  } while (fgets(buf,sizeof(buf),stdin), buf[0] == 'y');

  exit (puts("Bye") == EOF);
}

Обилия инклюдов не пугайтесь, большая часть  на нужны, просто скопировал для этого
тестика из другой программы.
А вот и иллюстация
avp@avp-xub11:~/src/ig/tst$ gcc th.c -pthread
.....
avp@avp-xub11:~/src/ig/tst$ ./a.out 381
create: Cannot allocate memory
avp@avp-xub11:~/src/ig/tst$ ./a.out 380
run 380 nth = 380
join 380 nth = 0
Again ?
y
run 380 nth = 380
join 380 nth = 0
Again ?
y
run 380 nth = 380
join 380 nth = 0
Again ?
y
run 380 nth = 380
join 380 nth = 0
Again ?
.
Bye
avp@avp-xub11:~/src/ig/tst$ ./a.out 380
run 380 nth = 380
join 380 nth = 0
Again ?
y
run 380 nth = 380
join 380 nth = 0
Again ?
.
Bye
avp@avp-xub11:~/src/ig/tst$ ./a.out 381
create: Cannot allocate memory
avp@avp-xub11:~/src/ig/tst$

IMHO видно, что если ресурса почти достаточно, то после завершения потоков он опять
высвобождается и повторно используется (по крайней мере в такой же ситуации).
UPD-1
@margosh, у меня в линуксе не растет. Добавил функцию
// returns second field for last line selected by  'what'
static int
pri_mem (int pid, char **what)
{
  char path[1000];
  int  res = 0;

  sprintf (path,"/proc/%d/status",pid);
  FILE *in = fopen(path,"r");
  if (!in) {
    perror(path);
    return;
  }
  while (fgets(path,1000,in)) {
    char **w = what;
    while (*w) {
      if (strncasecmp(path,*w,strlen(*w)) == 0) {
        fputs(path,stdout);
        char dummy[1000];
        sscanf(path,"%s %d",dummy,&res);
        break;
      }
      w++;
    }
  }
  fclose(in);

  return res;
}

и чуть изменил main(), теперь печатает память перед каждым циклом
avp@avp-xub11:~/src/ig/tst$ gcc th.c -pthread
avp@avp-xub11:~/src/ig/tst$ ./a.out 380
VmPeak:     2252 kB
VmSize:     2252 kB
VmHWM:       312 kB
VmRSS:       312 kB
VmStk:       136 kB
run 380 nth = 380
loop 0: join 380 nth = 0
Exit ?

VmPeak:  3116732 kB
VmSize:    35044 kB
VmHWM:      2180 kB
VmRSS:       680 kB
VmStk:       136 kB
run 380 nth = 380
loop 1: join 380 nth = 0
Exit ?

VmPeak:  3116736 kB
VmSize:    35044 kB
VmHWM:      2192 kB
VmRSS:       692 kB
VmStk:       136 kB
run 380 nth = 380
loop 2: join 380 nth = 0
Exit ?

VmPeak:  3116736 kB
VmSize:    35044 kB
VmHWM:      2192 kB
VmRSS:       692 kB
VmStk:       136 kB
run 380 nth = 380
loop 3: join 380 nth = 0
Exit ?

и дальше
VmPeak:  3116736 kB
VmSize:    35044 kB
VmHWM:      2192 kB
VmRSS:       692 kB
VmStk:       136 kB
run 380 nth = 380
loop 29: join 380 nth = 0
Exit ?
VmPeak:  3116736 kB
VmSize:    35044 kB
VmHWM:      2192 kB
VmRSS:       692 kB
VmStk:       136 kB
run 380 nth = 380
loop 30: join 380 nth = 0
Exit ?
VmPeak:  3116736 kB
VmSize:    35044 kB
VmHWM:      2192 kB
VmRSS:       692 kB
VmStk:       136 kB
run 380 nth = 380
loop 31: join 380 nth = 0
Exit ?
y
Bye
avp@avp-xub11:~/src/ig/tst$

IMHO не растет. Попробуем с небольшим количеством потоков
avp@avp-xub11:~/src/ig/tst$ ./a.out 30
VmPeak:     2252 kB
VmSize:     2252 kB
VmHWM:       316 kB
VmRSS:       316 kB
VmStk:       136 kB
run 30 nth = 30
loop 0: join 30 nth = 0
Exit ?

VmPeak:   248132 kB
VmSize:    35044 kB
VmHWM:       728 kB
VmRSS:       628 kB
VmStk:       136 kB
run 30 nth = 30
loop 1: join 30 nth = 0
Exit ?

VmPeak:   248136 kB
VmSize:    35044 kB
VmHWM:       740 kB
VmRSS:       640 kB
VmStk:       136 kB
run 30 nth = 30
loop 2: join 30 nth = 0
Exit ?

.......
.......

loop 15: join 30 nth = 0
Exit ?

VmPeak:   248136 kB
VmSize:    35044 kB
VmHWM:       740 kB
VmRSS:       640 kB
VmStk:       136 kB
run 30 nth = 30
loop 16: join 30 nth = 0
Exit ?

VmPeak:   248136 kB
VmSize:    35044 kB
VmHWM:       740 kB
VmRSS:       640 kB
VmStk:       136 kB
run 30 nth = 30
loop 17: join 30 nth = 0
Exit ?
y
Bye
avp@avp-xub11:~/src/ig/tst$

Возможно проблема в FreeBsd.


Ответ 2

Странно, что никто не сказал про pthread_detach(). Помнится если его не запускать
память выделенная под поток не освобождается и очень шустро растет, что очень заметно
например в htop. Я вызываю эту штуку после pthread_create().
pthread_t restrict;
if(pthread_create(&restrict, ...)) return 0;
pthread_detach(restrict);
return 0;

"Функция pthread_join блокирует работу вызвавшей ее нити исполнения до завершения
thread'а с идентификатором thread." Не вижу никакой связи с использованием памяти.
Она тут не при чем.


Ответ 3

лимит комментов исчерпан.
@avp, -D_THREAD_SAFE не спас. Возможно, прийдется пересмотреть логику очищения, в
любом случае попробую  и с detach для разнообразия, вдруг изменится чего. да, join
сейчас только 1 поток делает, когда получает признак через pipe(), как Вы мне когда-то
подсказали уже, за что большое спасибо :)

Переполнение/утечка памяти программы - C#

#c_sharp #net #многопоточность #память #парсер

Пишу программу для парсинга одного сайта. Сам сайт парсится с помощью CsQuery. Нужно
за раз обработать нужный диапазон страниц сайта. Задаётся начальная и конечная ссылки
для парсинга и программа в несколько потоков перебирает все страницы в диапазоне и
извлекает нужную информацию в List, что бы после окончания сохранить всё в файл. Нужное
количество потоков запускается, и они по очереди берут из счётчика текущей страницы
свой номер и работают с ним. В потоках написан цикл While, что бы они не закрывались,
пока не спарсили последнюю страницу. После окончания парсинга отдельно сохраняется
вся информация в List. Но проблема в том, что парсится будут большие диапазоны страниц
больше миллиона, а при тестовом запуске на диапазоне в 10 000 страниц программа начинает
занимать в памяти больше 1,5 гигабайт. В отдельной программе пробовал заполнять List
случайными данными, по типу тех, что должны были быть извлечены. Добавил 100 000 строк,
и размер оперативной памяти, используемой программы не превышал 100 мегабайт. Парсинг
так же работает правильно, никаких избыточных данных он не добавляет. Я грешу на мою
неправильную работу с потоками, и то, что сборщик мусора не уничтожает данные с прошлых
проходов парсинга. Пробовал разные способы так и не решил проблему с утечкой памяти.
Помогите найти ошибку, или подсказать более правильный метод работы с потоками. Код
прикладываю.

class Program
{
    static int begin_of_post = 2950774;      //начальный индекс постов
    static int end_of_post = 2951774;        //конечный индекс
    static int current_post;                 //текущий пост для потоков

    static List list_posts = new List();   //список хранения данных
о постах

    static void Main(string[] args)
    {
        ServicePointManager.DefaultConnectionLimit = 1000000000;   // количество
одновременных соединений

        current_post = begin_of_post;

        Thread my_tr;                               
        for (int i = 0; i < 10; i++)            //запуск потоков
        {
            my_tr = new Thread(parse_site);
            my_tr.Start();
        }

        Console.ReadLine();
        save_to_file();
    }

    static void parse_site()
    {
        while (current_post <= end_of_post)
        {
            int link_to_post =current_post;                 //ссылка на пост
            Interlocked.Increment(ref current_post);        //инкремент счётчика

            CQ cq;
            try
            {
                cq = CQ.CreateFromUrl("http://site.ru/" + link_to_post);        //
загрузка кода страницы
            }
            catch
            {
                Console.WriteLine("Error " + link_to_post);
                continue;
            }

            string post_info;
            ...
            //сам парсинг сайта
            ...

            int current = int.Parse(link_to_post) - begin_of_post;          
            int end = end_of_post - begin_of_post;
            Console.WriteLine("Обработана ссылка " + current.ToString() + " ИЗ "
+ end.ToString());

            Thread my_tr_save=new Thread(save_post);
            my_tr_save.Start(post_info);
        }
    }

    static void save_post(object post_info)
    {
        ...
        // Парсинг информации о странице
        ...

        lock (list_posts)
        {
            list_posts.Add(post_info.ToString());
        }
    }      

    static void save_to_file()
    {
                    ...
        //сохранение строк list_posts в файл
                    ...
    }
}

    

Ответы

Ответ 1

Вообще для того чтобы судить об утечке, нужно использовать профайлер, сделать два
внэпшота (до и после) и посмотреть, что отнимает память.



Какие навскидку есть проблемы в этом коде:


Внутри каждого из потоков, читающих страницы, вы в цикле непрерывно создаете новые
потоки:

Thread my_tr_save=new Thread(save_post);
my_tr_save.Start(post_info);


Во-первых, вы плодите множество потоков, а они занимают память. Во-вторых, это избыточно,
потому что вы и так уже внутри отдельного потока. И разносить в разные потоки парсинг
и сохранение для начала нет смысла.
К переменной current_post обращаются разные потоки, причем небезопасным способом.
Теоретически может случиться так, что каждый пост обрабатывается несколько раз и вы
получаете дубликаты страниц в вашем конечном списке, а значит, лишнюю память. Вам нужно
атомарно выполнять условие current_post <= end_of_post с последующим инкрементом и
возвращать актуальное значение, а в теле цикла пользоваться эти значением.

static bool HasPostsToParse(out current)
{
    lock (lockObject)
    {
        // к переменной current_post обращаетесь только в этом методе
        if (current_post <= end_of_post)
        {
            current = ++current_post;
            return true;
        }
        else
        {
            current = current_post;
            return false;
        }
    }
}

static void parse_site()
{
    int current;
    while (HasPostsToParse(out current))
    {
        // используете локальную переменную current
    }
}


Ответ 2

в вашем случае у вас рождаются новые потоки, каждому из которых выделяется стек по
4 мегабайта и ни один из потоков не может закончить работу и освободить память, потому
что каждый из потоков закручивается while (current_post <= end_of_post) аж до конца
выполнения всей работы вообще. Поэтому у вас будет постоянный прирост памяти за счет
стеков аж до конца работы

более правильный метод с потоками это TPL + правильное понимание IO-bound потоков
и перелопатить весь этот миллион страниц можно одними потоками из пула.

автор просил примеров как лучше делать в таких случаях (конечно парсер автора может
не позволять этого)

 class SomeNetParser
{
    private const int ThreadCount=20;
    private CountdownEvent _countdownEvent;
    private SemaphoreSlim _throttler;

    public void Check(IList urls)
    {
        _countdownEvent = new CountdownEvent(urls.Count);
        _throttler = new SemaphoreSlim(ThreadCount); 

        foreach (var url in urls)
        {
            await _throttler.WaitAsync(ct);
            ProccessUrl(url);
        }
     _countdownEvent.Wait();
    }

    private async void ProccessUrl(string url)
    {
        try
        {
            var page = await new WebClient().DownloadStringTaskAsync(new Uri(url)); 
            ProccessResult(page);
        }
        finally
        {
            _semaphoreSlim.Release();
            _countdownEvent.Signal();
        }
    }

    private void ProccessResult(string page){/*....*/}
}


нужно не забыть метод Check вызвать не UI потоке. CountdownEvent нужен, чтобы после
выхода из цикла дождался последней задачи.
минусом данного решения является то, что он удерживает 1 поток.

CountdownEvent можно выбросить и содержимое Check заменить на

var allTasks = new List();

foreach (var url in urls)
{
    await _throttler.WaitAsync(ct);
    allTasks.Add(ProccessUrl(url));
}

await Task.WhenAll(allTasks);


и ProccessUrl должен возвращать Task
В этом случае allTasks  будет накапливаться миллионом экземпляров Task и я даже не
знаю, как быстро Task.WhenAll будет их проверять

Есть еще вариант с LINQ, но он сложно понимаемый для новичков.

зы: WebClient плохо подходит для этого. Он написан неправильно и выполняет часть
своей работы с потоке который его вызвал и это так и не починили. HttpClient лучше
подходит.


Ответ 3

Для параллельной обработки данных в заданном диапазоне можно использовать Parallel.For.
Если взять части из вашего кода, то будет примерно так: 

using System.Threading.Tasks;
using System.Collections.Concurrent;
// ...

int begin_of_post = 2950774;      //начальный индекс постов
int end_of_post = 2951774;        //конечный индекс

var list_posts = new BlockingCollection();
Parallel.For(begin_of_post, end_of_post, (current_post) => {
    // ...
    var cq = CQ.CreateFromUrl("http://site.ru/" + link_to_post);
    list_posts.Add(link_to_post);
    // ... код для парсинга и т.д.
    save(file_name);
});

save_to_file(list_posts);




UPDATE:

Если надо скачать много страниц, распарсить их и сохранить в файлы, а также получить
лог, то можно сделать примерно так: 

public class App {
    BlockingCollection log;      // для синхронизации вывода в log
    public Run(int start, int end) {
        log = new BlockingCollection();
        Task.Run(() => {
            foreach(var s in log) {
                // тут пишем в log.txt
            }
        });
        Task.Factory.StartNew(() => {
            // для каждого запроса создаем отдельный Task   
            foreach (var page in Enumerable.Range(start, end))
                Task.Factory.StartNew(() => Download(page), 
                   TaskCreationOptions.AttachedToParent);
        }).Wait();   // ждем завершение всех запущенных Task'ов

        log.CompleteAdding();   // завершим Task логирования
    }
    void Download(int page) { // выполняется в отдельном потоке
        var url = "http://...." + page;
        log.Add(url);
        try {
            var html = RequestPage(url);
            Task.Factory.StartNew(() => Parse(url, html), 
               TaskCreationOptions.AttachedToParent);
        } catch(...) {
            log.Add("fail");
        }
    }
    void Parse(string url, string html) { // выполняется в отдельном потоке 
        // тут парсим html и сохраняем его в файл
    }
}

Регистры (теоретический вопрос)

#ассемблер #память #асинхронность #процесс #теория

Здравствуйте, извиняюсь за возможно глупый вопрос, но скажите пожалуйста где располагаются
регистры eax, ebx, ecx, edx, edi, esi, в оперативной памяти или процессоре?

Сам вопрос появился после того как я подумал, что если я не чего не путаю, то регистры
всегда вроде-бы располагались в процессоре (ну если верить книжкам), но я не могу понять
одного, как десятки процессов используют эти регистры грубо говоря асинхронно, процессор
же не может разорваться на каждый процесс. Ну и вот с этого момента мне стало очень
интересно как так может быть и я решил спросить у профессионалов.
    

Ответы

Ответ 1

регистры располагаются, конечно, в процессоре (если речь о современных распространённых
процессорах).

попеременно же используются они разными процессами благодаря механизму многозадачности.



в грубом приближении:

внутри процессора есть таймер, который время от времени посылает процессору сигнал
(«прерывание»), при получении которого процессор сохраняет текущее содержимое всех
регистров в стек (находится в оперативной памяти, обычно каждый процесс имеет собственный
стек; а сохраняются туда регистры не только с данными, но и со всякой контрольно-управляющей
информацией, типа ip — instruction pointer — адресом следующей выполняемой команды)
и передаёт управление по адресу обработчика данного прервывания (обработчик обычно
реализован в ядре операционой системы).

обработчик выбирает, какой процесс следует запустить следующим (какому процессу отдать
очередной «квант времени»), и даёт процессору команду «загрузить в регистры то, что
сохранённо там-то».

восстановленный же из стека процесс продолжает работу «как ни в чём не бывало», до
следующего срабатывания таймера.


Ответ 2

Регистры в процессоре. Многозадачность - фича ОС, которая сохраняет контекст процесса,
включая регистры. Так и получается что один набор регистров вполне досаточен для многих
процессов.

Семантика работы\хранения UpCast“инга \ DownCast”инга в CLR

#c_sharp #память #clr #типы

Начнем с теории.
Допустим,имеется следующие классы:  

class A{}
class B : A{}
class C : B{}


Далее,мы делаем UpCast :  

A a1 = new C();  


Будет ли следующее утверждение верным : объект a1 является объектом типа C,и базовым
классом для него является тип А (то бишь вверх по иерархии) !?  

Далеко не уходя от кассы, представьте что добавили в код следующее: 

class A
{
    public virtual void Method()
    {
        Console.WriteLine("Method A invoked");
    }
}
class B : A
{
    public new virtual void Method()
    {
        Console.WriteLine("Method B invoked");
    }
}
class C : B
{
    public override void Method()
    {
        Console.WriteLine("Method C invoked");
    }
}


Что будет выведено на экран ?
В первую очередь покажется,что тут все очевидно,и вывод выходе получим :  

Method A invoked
Method A invoked
Method С invoked
Method C invoked   



   Но на самом то деле,мы получим : Method A invoked Method A invoked Method A invoked
Method C invoked


Исходя из этой логики,выходит что мое предыдущее высказывание не верное,и это значит,что
все таки базовым классом для C,является B ?  



Теперь перейдем к другой части вопроса.
К примеру имеем код:  

  class Program
    {
        static void Main(string[] args)
        {
            //объект типа класса А
            A a = new A();
            //объект типа класса B
            B b = new B();
            //UpCast, который равен объекту "b"
            A a1 = b;
            //UpCast как отдельный объект
            A a2 = new B();
            //DownCast, который равен объекту "а1"
            B b1 = (B)a1;

            B b2 = a as B; // вернет Null, т.к. DownCast
            //без предварительного UpCast не возможен

            // B b2 = new A(); - невозможно из за безопасности типов

            //сравниваем b с а1,видим что типы идентичны.
            Console.WriteLine(b.GetType() == a1.GetType());
            //сравниваем а2 с а1,видим что типы идентичны.
            Console.WriteLine(a2.GetType() == a1.GetType());
            //сравниваем b1 и а1,видим что типы идентичны
            Console.WriteLine(b1.GetType() == a1.GetType());

            //Проверяем сами обьекты,вернет True
            Console.WriteLine(a1.Equals(b));
            //вернет False,но реализация этих объектов идентична
            Console.WriteLine(a2.Equals(a1));
            //Вернет True
            Console.WriteLine(b1.Equals(a1));

            Console.ReadKey();
        }
    }
    class A
    {
    }
    class B : A
    {
    }  




Так все же,что происходит за кулисами?
Как при UpCast"е \ DownCast"е ,два одинаковых объекта(точнее две ссылки,указывающие
на один и тот же объект),имеют различную реализацию(да,да - это полиморфизм). За счет
чего это достигается(то бишь,как CLR реализует эту модель поведения) и как примерно
выглядит все это чудо-юдо в самой среде CLR ? Как выглядит "наследование" внутри CLR
между типами?
    

Ответы

Ответ 1

По порядку:


  Будет ли следующее утверждение верным : объект a1 является объектом типа C,и базовым
классом для него является тип А (то бишь вверх по иерархии) !?


Нет. Корректным утверждением будет следующее: объект a1 является объектом типа C,и
базовыми классами для него являются типы B и А.

Разница большая, поскольку каждый тип в иерархии наследования может привносить новые
аспекты поведения.

Теперь дальше:

class A
{
    public virtual void Method()
    {
        Console.WriteLine("Method A invoked");
    }
}
class B : A
{
    public new virtual void Method()
    {
        Console.WriteLine("Method B invoked");
    }
}
class C : B
{
    public override void Method()
    {
        Console.WriteLine("Method C invoked");
    }
}


А данном примере сложно сказать, что именно хотел сказать автор этих строк с точки
зрения бизнес-логики, но звучит это примерно так: класс B добавляет новый метод Method,
но, к сожалению, он использует метод, имя которого уже есть в базовом классе. Но класс
B хочет не "подменить" поведение метода из базового класса, а создать свой собстенный
метод, который ничего не имеет общего с методом базового класса, кроме имени.

Подобная практика приводит к неоднозначному поведению, поскольку теперь выбор метода
определяется не только динамическим типом объекта (типом времени исполнения), но и
типом переменной (типом, известным компилятору): если используется переменная типа
A, то будет вызван метод из класса A. Если же тип переменной - это B или C, то будет
использоваться другая ветка методов (ниже будет объяснение, почему это так).

Другими словами, с точки зрения метода Method существует две ветки: одна начинается
типом А и им же и ограничивается, и есть другая полиморфная ветка, которая начинается
в типе B и продолжается в наследнике - типе С.

Теперь немного о том, как это устроено в CLR.

Для каждого типа CLR хранит табличку с методами (Method Table), где каждая запись
описывает отельный метод - его сигнатуру и признак того, переопределяет ли данный слот
метод из базового класса.

Когда вы объявили метод с приставкой new в классе B, CLR добавила "новый" метод в
табличку, при этом пометила этот метод, как новый, не связанный с методом из базового
класса. В случае же класса С, метод Method в табличке методово типа C помечен, как
полиморфный, т.е. переопределяющий поведение непосредственного базового класса.

Теперь стоит сказать, как происходит разрешение метода во время исполнения: в случае
вызова a.Method будет вначале определен статический тип переменной a, после чего в
таблице методов будет найден метод Method. Если статический тип переменной - это A,
то вначале будет просмотрена таблица методов типа A. И в этом случае CLR увидет, что
этот метод виртуальный. После чего будет определен реальный тип объекта (например,
тип C) и CLR посмотрит, а есть ли у этого типа переопределение метода, объявленного
в типе A. CLR получит отрицательный ответ, поскольку тип C не переопределяет метод
Method, объявленный в типе A (ведь этот тип переопределяет метод Method типа B).

Вот и получается, что результат разрешения имени метода у нас теперь зависит не только
от типа времени исполнения, но и от типа переменной времени компиляции.

Выделение памяти под неинициализированные переменные

#c #память

Подскажите пожалуйста, выделяется ли память под переменные если они просто объявлены,
но им не присвоены конкретные значения. Например, написал просто int x,y,z и при этом
их не использовал никак по ходу программы.
    

Ответы

Ответ 1

Если не использовали вообще - то умный оптимизатор их выбросит, не выделив память.
Если вы использовали x для чтения без предварительной записи, а перед этим просто написали
int x; не в глобальной области видимости - место будет выделено, но не инициализировано,
о чем умный компилятор должен бы предупредить - об использовании неинициализированной
переменной.

Кусочек из книжки "С. Справочник. Полное описание языка":

Объявление объекта является определением, если оно выделяет память для объекта. Объявления,
которые включают инициализаторы, всегда являются определениями. Кроме того, все объявления
в блоке функции являются определениями, если только они не содержат спецификатор класса
памяти extern. Вот несколько примеров:

int a = 10;         // Определение a.
extern double b[];  // Объявление массива b, определенного
                    // в другом месте программы.
void func()
{
    extern char c;  // Объявление, но не определение c.
    static short d; // Определение d.
    float e;        // Определение e.
    /* ... */
}


Если вы объявляете объект за пределами всех функций, без инициализатора и без спецификатора
памяти extern, такое объявление является предполагаемым определением (tentative definition).
Вот несколько примеров:

int i, v[];   // Предполагаемые определения i, v и j.
static int j;


Предполагаемое определение идентификатора остается простым объявлением, если единица
трансляции содержит еще одно определение того же самого идентификатора. Если же нет,
то компилятор ведет себя так, как будто предполагаемое определение включает инициализатор
с нулевым значением, что делает его определением. Таким образом, переменные i и j типа
int в предыдущем примере, идентификаторы которых объявляются без инициализаторов, неявно
инициализируются значением 0, а массив v с типом элементов int имеет один элемент с
исходным значением 0.


Ответ 2

Вы неявно предполагаете, что компилятор честно выделяет память под каждую переменную
в отдельности. Это уже давно не так.

Современные оптимизаторы могут поместить любую переменную в регистры, в общую область
памяти с другой переменной, если их время жизни не пересекается, или вовсе преобразовать
код и исключить переменную. Поэтому не имеет смысла экономить на переменных, компилятор
всё сделает правильно и экономно.



Пример: вот такой код

int f()
{
    int x = 5, y = 8;
    x += y;
    y = 7 * x;
    return x + y;
}


intel compiler 17 компилирует в

push      104
pop       rax
ret


а gcc 6.3 в

mov     eax, 104
ret


Вы видите, что компилятор выкинул вообще все переменные и вычисления.


Ответ 3

Например, такой код завершается аварийно (MinGW)

int main()
{
    double v[1000000];
    return 0;
}


В данном случае видимо выделяется. По ходу переполнение стека.

Использование “new []” вместо “new” в С++

#cpp #память

Можно ли использовать new [] вместо new? К примеру:

int main()
{
    int q = 1;
    int *mass = new int [q];
    ...
    delete [] mass;
}


Спрашиваю потому, что хочется сделать код более универсальным, чтобы каждый раз не
делать проверки на значения переменной q, где она может быть больше единицы или равной ей.
Будет ли такой код корректно функционировать? И не будет ли такой стиль считаться
дурным тоном?
    

Ответы

Ответ 1

Такой способ создания одиночных объектов непригоден в случаях, когда необходимо полиморфное
удаление полиморфных объектов. Полиморфное удаление возможно только через new/delete,
но не через new[]/delete[].

Также такой способ создания одиночных объектов приведет к повышенному расходу памяти
в случаях, когда объект имеет нетривиальный деструктор.


Ответ 2

Никто не мешает писать new T[n], где n == 1.

Однако само по себе использование new T[n] и new T считается дурным тоном, т.к. есть
std::vector и std::make_unique.

В частности С++ Core Guidelines не рекомендуют использование "naked new":


  ES.60: Avoid new and delete outside resource management functions
  
  Reason
  Direct resource management in application code is error-prone and tedious.

Как работает функция memmove в C?

#c #указатели #память

Всем привет!

Пытаюсь разобраться как работает функция memmove из стандартной библиотеки C. 

Сама функция:

void    *ft_memmove(void *dst, const void *src, size_t len)
{
    const char  *s;
    const char  *lasts;
    char        *d;
    char        *lastd;

    d = dst;
    s = src;
    if (d < s)
        while (len--)
            *d++ = *s++;
    else
    {
        lasts = s + (len - 1);
        lastd = d + (len - 1);
        while (len--)
            *lastd-- = *lasts--;
    }
    return (dst);
}


Помогите, пожалуйста, понять, что происходит в данной части функции:

else
        {
            lasts = s + (len - 1);
            lastd = d + (len - 1);
            while (len--)
                *lastd-- = *lasts--;
        }

    

Ответы

Ответ 1

lasts = s + (len - 1);  // Указатель на последний байт блока s
lastd = d + (len - 1);  // Указатель на последний байт блока d
while (len--)           // len раз
    *lastd-- = *lasts--;// выполняем копирование из блока d в блок s
                        // После копирования байта указатели уменьшаются


т.е. простое копирование памяти не "слева направо", а "справа налево".

Смысл всего действа - чтоб не затереть копированием нужное при перекрывающихся областях
памяти.


Ответ 2

Если эта ft_memmove действительно является реализацией (или частью реализации?) стандартной
функции memmove, то надо заметить, что реализация функций стандартной библиотеки языка
С не обязана быть написана на языке С и не подчиняется требованиям языка С. 

Если рассматривать приведенный вами участок кода как код на языке С, то он внешне
выполняет (пытается выполнять) копирование участка памяти "в обратном направлении"
- от старших адресов к младшим. Однако с точки зрения языка С приведенный код делает
это неправильно - на последней итерации цикла копирования происходит применение оператора
-- к значениям указателей lastd и lasts, потенциально указывающих в этот момент на
начала неких массивов. Это формально приводит к неопределенному поведению.

Так что с точки зрения формального языка С код является некорректной реализацией
memmove. Если этот код действительно позаимствован из реализации стандартной библиотеки,
то это не С, а нечто внешне С-подобное. Чтобы говорить о том, что именно он делает,
надо знать особенности поведения той платформы для которой этот код написан. Если же
это пользовательский код, то вышеуказанная проблема делает его просто некорректным.

Как осуществить слияние k сортированных списков

#python_3x #сортировка #list #память #время

Даны k отсортированных в порядке неубывания массивов натуральных чисел, каждое из
которых не превосходит 100. Требуется построить результат их слияния: отсортированный
в порядке неубывания массив, содержащий все элементы исходных k массивов.

Длина каждого массива не превосходит 10 ⋅ k.

Постарайтесь, чтобы решение работало за время k ⋅ log(k) ⋅ n, если считать, что входные
массивы имеют длину n.

Формат ввода

Первая строка входного файла содержит единственное число k, k ≤ 1024.

Каждая из следующих k строк описывает по одному массиву. Первое число каждой строки
равняется длине соответствующего массива, оставшиеся числа этой строки описывают значения
элементов этого же массива. Элементы массивов являются натуральными числами и не превосходят 100.

Формат вывода

Выходной файл должен содержать отсортированный в порядке неубывания массив, содержащий
все элементы исходных массивов.

Пример

Ввод

4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84

Вывод

1 2 4 8 16 20 26 42 58 61 64 65 69 84 86 88 96 96

Ограничение по времени выполнение скрипта 1 сек. для любого теста, ограничение по
используемой памяти: 10 МБ

Вот мой код:

import sys

int_str = ''
n = int(sys.stdin.readline().strip())
for i in range(int(n)):
    s = sys.stdin.readline().strip() + ' '
    count = int(s[:s.find(' ')])
    p, j = 0, 0
    for j in range(s.__len__()):
        if s[j] == ' ':
            p += 1
        if p == count+1:
            break
    int_str += s[s.find(' '):j]
    del (s,)

for i in sorted(int_str.lstrip().split(' '), key=lambda x: int(x) if x.isdigit() else 0):
    print(i, end=" ")


Ещё один вариант

import sys

n = int(sys.stdin.readline().strip())
int_list = []
for i in range(n):
    input = sys.stdin.readline().strip()
    data = list(map(int, input.split()))
    input = None
    n = data[0]
    a = data[1:n+1]
    int_list.extend(a)
    data = None

int_list.sort()

for li in int_list:
    sys.stdout.write(str(li) + ' ')
sys.stdout.write('\n')


Гномья сортировка

import sys

int_list = []
t = [0] * 101
n = int(sys.stdin.readline().strip())
for i in range(int(n)):
    s = sys.stdin.readline().strip()
    try:
        num = int(s[:s.find(' ')])
    except ValueError:
        continue
    for index, value in enumerate(s.split(' ')):
        if index == 0:
            continue
        elif index == num + 1:
            break
        try:
            t[int(value)] += 1
        except ValueError:
            pass
    del s

res = []
for i in range(101):
    res += [i] * t[i]

for r in res:
    print(r, end=' ')


Memory Limit и Time Limit близко
    

Ответы

Ответ 1

Так как в задаче есть ограничение на элементы массива:


  массивов натуральных чисел, каждое из которых не превосходит 100.


то можно применить сортировку подсчётом, которая работает за линейное время.

Но для C# возникает ещё одна проблема - это создание массива строк при считывании
данных, которые на больших данных используют > 10Мб памяти. Я решила эту проблему с
помощью запуска сборщика мусора.
Моё решение:

using System;
using System.IO;

namespace ConsoleApp
{
    class Program
    {

        static void Main(string[] args)
        {
            short[] digitsCount = new short[101];
            short k = Convert.ToInt16(Console.ReadLine());

            string[] values;
            for (short i = 0; i < k; i++)
            {
                values = Console.ReadLine().Split(' ');

                for (short j = 1; j < values.Length; j++)
                {
                    digitsCount[Convert.ToByte(values[j])]++;
                }

                GC.Collect();
            }

            using (StreamWriter sw = new StreamWriter("output.txt"))
            {
                for (short i = 0; i < digitsCount.Length; i++)
                {
                    for (short j = 0; j < digitsCount[i]; j++)
                    {
                        sw.Write(i + " ");
                    }
                }
            }

        }
    }
}


Удачи на собеседовании!


Ответ 2

Сложность k * n

Time Limit помогло убрать периодический вывод буфера, а не накопление его до N 

k = int(input())

count = {str(i): 0 for i in range(100)}

total = 0
for list_index in range(k):
    a = input().split()
    size = int(a[0])
    total += size
    if size > 0:
        for i in range(1, size + 1):
            count[a[i]] += 1

buff = []
for i in range(100):
    c = str(i)
    if i % 10 and buff:
        print(' '.join(buff), end=' ')
        buff = []

    buff.extend([c] * count[c])

print(' '.join(buff))


Тест list + int() vs dict vs Counter

from timeit import timeit
from collections import Counter

n = 10000000
str_list = [str(x) for x in range(n)]

number = 10
print(timeit("""
for i in range(n):
    a[int(str_list[i]) % 100] += 1
""", setup='a = [0] * 100', number=number, globals=globals()))

print(timeit("""
for i in range(n):
    d[str_list[i % 100]] += 1
""", setup='d = {str(i): 0 for i in range(100)}', number=number, globals=globals()))


print(timeit("""
for i in range(n):
    d[str_list[i % 100]] += 1
""", setup='d = Counter(i for i in range(100))', number=number, globals=globals()))


PyPy 3.5.3 (не понятно, почему Яндекс его не добавили):

6.919497203998617
1.7934346760011977
5.253608144004829


Python 3.7

27.728900675007026
17.81548438500613
25.83648096800607


Ответ 3

Тоже столкнулся с этой задачей. Начал с Python 3.6. Пробовал сортировку подсчетом
и heapq.merge. Ни в какую не укладываюсь в 1 секунду на 20м тесте. Попробовал переписать
на Go и сортировку подсчетом. Результат по времени абсолютно такой же как на Python.
Видимо от языка не зависит.

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    const k = 100

    reader := bufio.NewReader(os.Stdin)

    arraysNumString, _ := reader.ReadString('\n')
    arraysNumString = strings.TrimSuffix(arraysNumString, "\n")

    arraysNum, err := strconv.Atoi(arraysNumString)
    if err != nil {
        panic(err)
    }

    var counter [k]int

    for i := 0; i < arraysNum; i++ {
        inputString, _ := reader.ReadString('\n')
        inputString = strings.TrimSuffix(inputString, "\n")

        inputArray := strings.Split(inputString, " ")

        for idx, i := range inputArray {
            if idx == 0 {
                continue
            }
            j, err := strconv.Atoi(i)
            if err != nil {
                panic(err)
            }
            counter[j]++
        }
    }

    for index, value:= range counter {
        for i := 0; i < value; i++ {
            fmt.Println(index)
        }
    }
}


Видимо нужно искать другой алгоритм или экономить на чтении строк.


Ответ 4

В задаче не оговорен запрет на использование стандартной библиотеки, поэтому моё
решение выглядит следующим образом (для Python 3.4.3):

from collections import Counter

k = int(input())
a = Counter()
for _ in range(k):
    a += Counter(map(int, input().split()[1:]))
for key, c in sorted(a.items()):
    print("{} ".format(key) * c, end="")


Ключевой момент здесь в том, что элементы в вводимых массивах не могут быть больше
100, а это значит, что количество ключей для Counter() не превысит это число. Даже
в худшем случае, сортировка сотни целочисленных значений - простая задача. 
Опасения у меня вызывал только момент с суммированием Counter(), однако даже в последнем
тесте, данный вариант затратил <5 mb памяти и уложился во время <0.7секунды.


Ответ 5

Реализация решения H. Case на основе встроенных типов.
Результаты - 0.522s, 4.36Mb.

n = int(input())

def counter_add(counter, value):
    if value in counter:
        counter[value] += 1
    else:
        counter[value] = 1

counter = dict()
for _ in range(n):
    ar = input().split()
    for i in ar[1:]:
        counter_add(counter, i)

for i in range(101):
    i = str(i)
    if i in counter:
        print(' '.join([i] * counter[i]), end=' ')


Ответ 6

Я решила вот так - по-простому:

k=int(input())

result={x:0 for x in range(0,101)}

for i in range(k):

    current=input().split()[1:]

    for j in range(len(current)):
        cj = int(current[j])
        result[cj] += 1

for key, v in result.items():
    print("{} ".format(key) * v, end="")


Ответ 7

А я решил пойти путем использования одномерных векторов. Жаль, что Я не принял импорт
NumPy... Пришлось тоже через сортировку подсчетом делать. Надеюсь, будет полезно и
на такой вариант взглянуть.

import sys
import numpy as np


k = sys.stdin.readline().strip()
A = np.array([], dtype=np.uint8)

for _ in range(int(k)):
    line = np.array(sys.stdin.readline().strip().split(" ")[1:], dtype=np.uint8)
    A = np.append(A, line)
    del line

A = np.sort(A, kind="mergesort")
A = A.tolist()
print(*A)