• Как передаются регистры в трансляторах? Как происходит переход, от виртуальных регистров к машинным?

    AshBlade
    @AshBlade
    Просто хочу быть счастливым
    Как перестать поддерживать ее, при выполнении клиентского кода в ходе динамической трансляции.

    Просто иметь оптимизации, которые знают, какой регистр какое название имеет.

    Раз уж ты поставил тег .NET, то у платформы есть свой JIT компилятор, который пишется под каждую платформу (CPU) и имеет знание о ее регистрах.
    Вот пример того, как это делается в исходном коде:
    1. Каждая платформа регистрирует свои регистры и информацию о них.
    #if defined(TARGET_XARCH)
    
    #if defined(TARGET_X86)
    /*
    REGDEF(name, rnum,   mask, sname) */
    REGDEF(EAX,     0,   0x01, "eax"   )
    REGDEF(ECX,     1,   0x02, "ecx"   )
    REGDEF(EDX,     2,   0x04, "edx"   )
    REGDEF(EBX,     3,   0x08, "ebx"   )
    REGDEF(ESP,     4,   0x10, "esp"   )
    REGDEF(EBP,     5,   0x20, "ebp"   )
    REGDEF(ESI,     6,   0x40, "esi"   )
    REGDEF(EDI,     7,   0x80, "edi"   )
    REGALIAS(RAX, EAX)
    REGALIAS(RCX, ECX)
    REGALIAS(RDX, EDX)
    REGALIAS(RBX, EBX)
    REGALIAS(RSP, ESP)
    REGALIAS(RBP, EBP)
    REGALIAS(RSI, ESI)
    REGALIAS(RDI, EDI)
    
    #else // !defined(TARGET_X86)
    
    /*
    REGDEF(name, rnum,   mask, sname) */
    REGDEF(RAX,     0, 0x0001, "rax"   )
    REGDEF(RCX,     1, 0x0002, "rcx"   )
    REGDEF(RDX,     2, 0x0004, "rdx"   )
    REGDEF(RBX,     3, 0x0008, "rbx"   )
    REGDEF(RSP,     4, 0x0010, "rsp"   )
    REGDEF(RBP,     5, 0x0020, "rbp"   )
    REGDEF(RSI,     6, 0x0040, "rsi"   )
    REGDEF(RDI,     7, 0x0080, "rdi"   )
    REGDEF(R8,      8, 0x0100, "r8"    )
    REGDEF(R9,      9, 0x0200, "r9"    )
    REGDEF(R10,    10, 0x0400, "r10"   )
    REGDEF(R11,    11, 0x0800, "r11"   )
    REGDEF(R12,    12, 0x1000, "r12"   )
    REGDEF(R13,    13, 0x2000, "r13"   )
    REGDEF(R14,    14, 0x4000, "r14"   )
    REGDEF(R15,    15, 0x8000, "r15"   )
    
    REGALIAS(EAX, RAX)
    REGALIAS(ECX, RCX)
    REGALIAS(EDX, RDX)
    REGALIAS(EBX, RBX)
    REGALIAS(ESP, RSP)
    REGALIAS(EBP, RBP)
    REGALIAS(ESI, RSI)
    REGALIAS(EDI, RDI)
    
    #endif // !defined(TARGET_X86)

    2. Для каждой платформы реализуются своя пара кодогенератор/эмиттер

    // Кодогенератор
    void CodeGen::genCodeForBinary(GenTreeOp* treeNode)
    {
        GenTree* op1 = treeNode->gtGetOp1();
        GenTree* op2 = treeNode->gtGetOp2();
    
        instruction ins = genGetInsForOper(treeNode->OperGet(), targetType);
    
        regNumber op1reg = op1->isUsedFromReg() ? op1->GetRegNum() : REG_NA;
        regNumber op2reg = op2->isUsedFromReg() ? op2->GetRegNum() : REG_NA;
    
        GenTree* dst;
        GenTree* src;
    
        // This is the case of reg1 = reg1 op reg2
        // We're ready to emit the instruction without any moves
        if (op1reg == targetReg)
        {
            dst = op1;
            src = op2;
        }
        // We have reg1 = reg2 op reg1
        // In order for this operation to be correct
        // we need that op is a commutative operation so
        // we can convert it into reg1 = reg1 op reg2 and emit
        // the same code as above
        else if (op2reg == targetReg)
        {
            dst = op2;
            src = op1;
        }
        // dest, op1 and op2 registers are different:
        // reg3 = reg1 op reg2
        // We can implement this by issuing a mov:
        // reg3 = reg1
        // reg3 = reg3 op reg2
        else
        {
            var_types op1Type = op1->TypeGet();
            inst_Mov(op1Type, targetReg, op1reg, /* canSkip */ false);
            regSet.verifyRegUsed(targetReg);
            gcInfo.gcMarkRegPtrVal(targetReg, op1Type);
            dst = treeNode;
            src = op2;
        }
        // try to use an inc or dec
        if (oper == GT_ADD && !varTypeIsFloating(treeNode) && src->isContainedIntOrIImmed() && !treeNode->gtOverflowEx())
        {
            if (src->IsIntegralConst(1))
            {
                emit->emitIns_R(INS_inc, emitTypeSize(treeNode), targetReg);
                genProduceReg(treeNode);
                return;
            }
            else if (src->IsIntegralConst(-1))
            {
                emit->emitIns_R(INS_dec, emitTypeSize(treeNode), targetReg);
                genProduceReg(treeNode);
                return;
            }
        }
        regNumber r = emit->emitInsBinary(ins, emitTypeSize(treeNode), dst, src);
    }
    
    // Эммитер
    /*****************************************************************************
     *
     *  Add an instruction with two register operands.
     */
    
    void emitter::emitIns_R_R(instruction ins, emitAttr attr, regNumber reg1, regNumber reg2, insOpts instOptions)
    {
        if (IsMovInstruction(ins))
        {
            assert(!"Please use emitIns_Mov() to correctly handle move elision");
            emitIns_Mov(ins, attr, reg1, reg2, /* canSkip */ false);
        }
    
        emitAttr size = EA_SIZE(attr);
    
        assert(size <= EA_64BYTE);
        noway_assert(emitVerifyEncodable(ins, size, reg1, reg2));
    
        /* Special case: "XCHG" uses a different format */
        insFormat fmt = (ins == INS_xchg) ? IF_RRW_RRW : emitInsModeFormat(ins, IF_RRD_RRD);
    
        instrDesc* id = emitNewInstrSmall(attr);
        id->idIns(ins);
        id->idInsFmt(fmt);
        id->idReg1(reg1);
        id->idReg2(reg2);
    
        if ((instOptions & INS_OPTS_EVEX_b_MASK) != INS_OPTS_NONE)
        {
            // if EVEX.b needs to be set in this path, then it should be embedded rounding.
            assert(UseEvexEncoding());
            id->idSetEvexbContext(instOptions);
        }
    
        UNATIVE_OFFSET sz = emitInsSizeRR(id);
        id->idCodeSize(sz);
    
        dispIns(id);
        emitCurIGsize += sz;
    }


    Дальше нам остается просто получить название регистра по его числу - это мы сделали на 1 шаге при их регистрации.

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

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Почему программы с одних адресов начинаются?

    Потому что часть программ просто линкуется в одни и те же адреса. Это т.н. position-dependent executable, их в принципе невозможно загрузить для исполнения по другому адресу, и до недавнего времени (по крайней мере в linux) это было поведением по умолчанию. Но вот уже лет 10 во многих дистрибутивах по умолчанию используются PIE -- position-independent executables, и если не выключен ASLR, то при каждой загрузке часть адреса выбирается случайно. Но это сделано не для улучшения поведения TLB а для безопасности, поскольку это затрудняет атаки использующие известные адреса загрузки кода.

    Вот есть Tlb, представим это как линейный массив, или c , если все адреса будут одинаковы. То Очевидно что tlb будет работать в 1% своего множества

    Нет, не очевидно. Потому что никто не делает процессоры с пропорциональным отображением всего адресного пространства на все записи TLB. Обычно индексом записи TLB являются младшие биты номера страницы. Т.е. две соседние страницы могут использовать два соседних индекса в TLB, а канал TLB на 256 записей может быть полностью использован всего-то непрерывным мегабайтом памяти в 4-КБайтных страницах.
    Ответ написан
    Комментировать
  • Как ос генерируют виртуальные адреса, по которым будет поиск, не физические? Почему программы с одних адресов начинаются?

    AshBlade
    @AshBlade
    Просто хочу быть счастливым
    Ты уже сказал про старшие 20 бит, скорее всего знаешь про сегментную организацию виртуальной памяти.
    20 бит используются в 32 битных системах, а сейчас большая часть 64 битная, но это не важно.
    Принцип следующий:
    Существует 3 таблицы:
    - PGD - Page Global Directory
    - PMD - Page Middle Directory
    - PTE - Page Table Entry

    Они иерархические, т.е. запись в PGD указывает на запись в PMD, а PMD - на PTE.
    В итоге, ты приходишь с 3 "числами" - индексы для этих таблиц и последовательно приходишь к нужной PTE.
    Но тебе нужно еще 4 число - смещение относительно полученного в PTE значения (там хранятся "начала" выделенных сегментов/интервалов памяти)
    Теперь последовательно запиши эти адреса и получишь виртуальный адрес.

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

    Как выделяется реальная память - деталь реализации, о которой знать не нужно.
    Если интересно - вот статья про память в линуксе.

    P.S. пример показан на C# - там собственная виртуальная память и GC. Поэтому показывает не то, что выделила ОС.
    Ответ написан
    Комментировать
  • Как сделать проект видимым для всех проектов в папке проектов, с автоматическим подключением?

    vabka
    @vabka Куратор тега C#
    Токсичный шарпист
    1. Можно поместить его в один солюшен - тогда IDE сама подскажет, если нужно импортировать
    2. Можно через файл directory.props https://learn.microsoft.com/ru-ru/visualstudio/msb... - это автоматически добавит элементы в csproj, если проекты находятся в одной папке.
    3. Можно завернуть в Nuget-пакет, как предлагает # - это не сделает добавление автоматическим, но добавлять будет их не сложно.
    Ответ написан
    1 комментарий
  • Как сохранить сбоку AssemblyBuilder? Где методы Save, DefineDynamicAssembly?

    AshBlade
    @AshBlade Куратор тега C#
    Просто хочу быть счастливым
    Дока, которую ты отправил, относится к .NET Framework.
    После перехода на .NET Core и .NET Standard эту тему перестали поддерживать.
    Работы по этому поводу сейчас ведутся и в .NET 9 должно появиться: https://github.com/dotnet/runtime/issues/92975
    Но если хочешь прямо сейчас, то вот репа с примером, как можно своими силами это сделать: https://github.com/dotnet/runtimelab/blob/feature/...
    Ответ написан
    Комментировать
  • Почему иногда не создаются автоматически свойства и команды mvc wpf?

    AshBlade
    @AshBlade Куратор тега C#
    Просто хочу быть счастливым
    Это называется IntelliSense - технология автодополнения кода.
    Иногда не срабатывает, потому что:
    - либо код неправильно написан и плагин его не понимает
    - либо индексация не закончилась
    - либо действительно нельзя ничего дополнить
    - либо ошибке в самом плагине

    По твоему вопросу возможно есть тут ответ - https://stackoverflow.com/questions/47595772/custo...
    Ответ: влияет расположение элементов в коде. по ответу все должно идти в таком порядке:
    1. Окно
    2. DataContext
    3. Твой код
    4. AttachedProperty
    Ответ написан
    Комментировать
  • Почему gpu вычисления ILGPU медленнее в 10 раз чем CPU?

    AshBlade
    @AshBlade Куратор тега C#
    Просто хочу быть счастливым
    Вот из-за этого:
    // Initialize ILGPU.
         Context context = Context.CreateDefault();
         Accelerator accelerator = context.CreateCLAccelerator(1);//context.GetPreferredDevice(preferCPU: false)  .CreateAccelerator(context);
    
         // Load the data.
         using  MemoryBuffer1D<float, Stride1D.Dense> deviceData = accelerator.Allocate1D(input);
         using MemoryBuffer1D<float, Stride1D.Dense> deviceOutput = accelerator.Allocate1D<float>(output);
    
         // load / precompile the kernel
         Action<Index1D, ArrayView<float>, ArrayView<float>> loadedKernel =
             accelerator.LoadAutoGroupedStreamKernel<Index1D, ArrayView<float>, ArrayView<float>>(Kernel);
    
    
         // finish compiling and tell the accelerator to start computing the kernel
             loadedKernel((int)deviceOutput.Length, deviceData.View, deviceOutput.View);
             accelerator.Synchronize();


    Объяснение: ты в каждом тесте постоянно создаешь новые объекты, которые необходимы для работы фреймворка. Это должно быть тяжелые объекты (много содержат, тяжело инициализируются).
    Вынеси их инициализацию из-вне метода в какой нибудь Setup метод. Раз уж ты пользуешься BenchmarkDotNet, то вот помощь с этим

    UPD: оптимизировал бенчмарк - теперь GPU быстрее
    public class SampleBenchmark
    {
        static void Kernel(Index1D i, ArrayView<float> data, ArrayView<float> output)
        {
            output[i] = data[i % data.Length];
        }
        public static IEnumerable<object[]> Arguments => new[] {new object[]{new float[1000000], new float[1000000]} };
        private float[] _outputBuffer = new float[1000000];
        private float[] _inputBuffer = new float[1000000];
        
        private Context? _context;
        private Accelerator? _accelerator;
        private Action<Index1D, ArrayView<float>, ArrayView<float>>? _loadedKernel;
        private MemoryBuffer1D<float, Stride1D.Dense>? _deviceData;
        private MemoryBuffer1D<float, Stride1D.Dense>? _deviceOutput;
        
        [GlobalSetup]
        public void Setup()
        {
            var random = new Random();
            for (var i = 0; i < _inputBuffer.Length; i++)
            {
                _inputBuffer[i] = random.NextSingle();
            }
            
            _context = Context.CreateDefault();
            _accelerator = _context.GetPreferredDevice(preferCPU: false).CreateAccelerator(_context);
            _loadedKernel = _accelerator!.LoadAutoGroupedStreamKernel<Index1D, ArrayView<float>, ArrayView<float>>(Kernel);
            _deviceData = _accelerator!.Allocate1D(_inputBuffer);
            _deviceOutput = _accelerator!.Allocate1D(_outputBuffer);
        }
    
        [GlobalCleanup]
        public void TearDown()
        {
            _context?.Dispose();
            _accelerator?.Dispose();
            _deviceData?.Dispose();
            _deviceOutput?.Dispose();
        }
        [ArgumentsSource(nameof(Arguments))]
        [Benchmark]
        public void GPUTest(float[] input, float[] output)
        {
            // finish compiling and tell the accelerator to start computing the kernel
            _loadedKernel!((int)_deviceOutput.Length, _deviceData.View, _deviceOutput.View);
            _accelerator!.Synchronize();
        }
    
        [Benchmark]
        [ArgumentsSource(nameof(Arguments))]
        public void CpuTest(float[] input, float[] output)
        {
            for (var i = 0; i < input.Length; i++)
            {
                output[i] = input[i];
            }
        } 
    }


    | Method  | input           | output          | Mean      | Error    | StdDev   |
    |-------- |---------------- |---------------- |----------:|---------:|---------:|
    | GPUTest | Single[1000000] | Single[1000000] |  61.18 us | 0.101 us | 0.095 us |
    | CpuTest | Single[1000000] | Single[1000000] | 243.54 us | 3.114 us | 2.600 us |
    Ответ написан
    2 комментария
  • Как вызвать функцию на представление с контроллера в mvc паттерне?

    yarosroman
    @yarosroman Куратор тега C#
    C# the best
    1. MessageBus как вариант.
    2. Делайте свой UserControl с таймером, который будет его обновлять как надо, а к нему уже данные привязывать необходимые.
    Ответ написан
    Комментировать
  • Как сделать шаблонный метод для мат операций с числами и Типом Vector2?

    AshBlade
    @AshBlade Куратор тега C#
    Просто хочу быть счастливым
    Интерфейсов чисел он не реализует. Есть 2 костыля:
    1. Вести словарь функций сложения
    var typeToFunc = new Dictionary<Type, AddFunc>() {{typeof(int), IntAdd}, {typeof(Vector2), Vector2Add}};
    
    var left = 123;
    var right = 14455;
    var result = Add(left, right);
    Console.WriteLine($"Результат сложения {left} и {right} = {result}");
    
    var leftVector = new Vector2(123, 55);
    var rightVector = new Vector2(55, 111);
    var resultVector = Add(leftVector, rightVector);
    Console.WriteLine($"Результат сложения {leftVector} и {rightVector} = {resultVector}");
    
    T Add<T>(T left, T right)
    {
        return ( T ) typeToFunc[typeof(T)](left, right);
    }
    
    object Vector2Add(object left, object right)
    {
        return ( Vector2 ) left + ( Vector2 ) right;
    }
    
    object IntAdd(object left, object right)
    {
        return (int) left + (int) right;
    }
    
    delegate object AddFunc(object left, object right);

    2. Создай монаду с int и Vector2
    var number = NumberOrVector2<int>.FromNumber(123);
    var newNumber = number.Add(() => 23, () => throw new InvalidOperationException("хранится число"));
    if (newNumber.TryGetNumber(out var result))
    {
        Console.WriteLine($"Получился результат: {result}");
    }
    else
    {
        Console.WriteLine($"Ошибка - хранился вектор");
    }
    
    public readonly struct NumberOrVector2<TNumber> where TNumber: unmanaged, INumber<TNumber>
    {
        private readonly TNumber _number;
        private readonly Vector2? _vector;
    
        private NumberOrVector2(TNumber number, Vector2? vector)
        {
            _number = number;
            _vector = vector;
        }
    
        public bool TryGetNumber(out TNumber number)
        {
            number = _number;
            return !_vector.HasValue;
        }
    
        public bool TryGetVector(out Vector2 vector)
        {
            vector = _vector.GetValueOrDefault();
            return _vector.HasValue;
        }
    
        public NumberOrVector2<TNumber> Add(Func<TNumber> numberAdd, Func<Vector2> vectorAdd)
        {
            if (_vector is {} vector)
            {
                return new NumberOrVector2<TNumber>(_number, vector + vectorAdd());
            }
    
            return new NumberOrVector2<TNumber>(_number + numberAdd(), null);
        }
        
        public static NumberOrVector2<TNumber> FromNumber(TNumber number)
        {
            return new NumberOrVector2<TNumber>(number, null);
        }
        
        public static NumberOrVector2<TNumber> FromVector(Vector2 vector)
        {
            return new NumberOrVector2<TNumber>(default, vector);
        }
    }
    Ответ написан
    Комментировать
  • Почему RenderTargetBitmap долго отрисовывается?

    @AlexHell
    судя по информации что я нашел https://stackoverflow.com/questions/56582013/why-t...
    RenderTargetBitmap doesn't take advantage of hardware rendering

    т.е. простыми словами - он рендерит на CPU, и в отличие от GPU рендеринга (шейдерами в играх как вы приводите сравнение), CPU рендеринг очень медленный, и не предназначен для высокого FPS, а скорее для оффлайн обработки как в граф редакторе без видеокарты :)
    Ответ написан
    Комментировать
  • Как прервать поток c#?

    vabka
    @vabka Куратор тега C#
    Токсичный шарпист
    Это вообще правильно?

    Да, это правильно и это по сути единственный адекватный способ отмены долгоиграющих операций.
    Когда-то давно у потоков был метод Abort, но его удалили, тк его использование очень часто приводило к неприятным багам.
    Ну и пихать проверку cancellation token повсюду не обязательно.
    Поток вызывает 1 функцию библиотечную неуправляемого кода, как ее прервать?

    Безопасно - никак, если эта неуправляемая функция не предоставляет интерфейс для отмены.
    Даже если бы и был способ (тот же Abort), то прерывание неуправляемого кода очень вероятно приведёт к утечке ресурсов (в лучшем случае не будет освобождена динамическая память)
    Ответ написан
    Комментировать
  • Как нормализовать массив значений в цветовое представление?

    @Mercury13
    Программист на «си с крестами» и не только
    Уровень 1. Чёрно-белое.
    R, G, B = round((x−min)·255 / (max − min))

    Уровень 2. Градиент между цветом X и цветом Y.
    t = (x−min) / (max − min)
    R = round(R1·t + R2·(1−t))
    G и B аналогично.

    Уровень 3. Учёт гамма-кривой монитора. Тут работаем сразу в двух цветовых пространствах: линейном от 0 до 1, и sRGB от 0 до 255.
    gamma = 2,2 — sRGB состоит из линейного и степенного участка, но неплохо приближается real_brightness = channel_%^gamma
    invGamma = 1/gamma
    функция toLinear(v) := (v/255)^gamma
    функция toSrgb(q) := (q^invGamma)·255 — в общем, обратная
    linR1 = toLinear(R1)
    linR2 = toLinear(R2)
    t = (x−min) / (max − min)
    R = round(toSrgb(linR1·t + linR2·(1−t)))

    Уровень 3.1. 16-битная аппроксимация (если важна скорость). В общем, линейное цветовое пространство — не дробные от 0 до 1, а целые от 0 до 65535.
    функция toLinear(i) := round(((i/255)^gamma)·65535)
    массив toSrgb(q) := ((q/65535)^invGamma)·255 — записывается в виде массива на 65536 величин
    linR1 = toLinear(R1)
    linR2 = toLinear(R2)
    K = (65535 / (max − min)
    t = round((x−min) * K)
    R = toSrgb(((linR1·t) + linR2·(65535−t) + 127) >> 16)

    Уровень 4. Сложный градиент из нескольких цветов.
    Для этого например, t=0 — синий, t=⅓ — зелёный, t=⅔ — жёлтый, t=1 — красный.
    Тогда прикидываем, в какой промежуток попадает t, получаем, например, t1=(t−⅓)·3, и дальше по уровню 3.
    Ответ написан
    Комментировать
  • Масштабирование времени? Как рассчитать положение точки при ускорении времени?

    Griboks
    @Griboks
    Используйте скорость на каждой итерации для моделирования движения.
    Шаг 1:
    V+=1=0+1=1
    X+=V=0+1=1

    Шаг 2:
    V+=1=1+1=2
    X+=V=1+2=3


    А теперь, ускорим время в 10 раз, пусть шаг физического движка будет 10сек=1сек, То что будет

    Не забывайте, что ускорение масшиабируется вместе с временем.

    Поэтому обычно пишут
    V=V0×dt
    Где V0 - скорость в нормальном ходе времени.
    Ответ написан
    2 комментария
  • Где ошибка, как из рекурсии цикл сделать?

    @mvv-rus
    Настоящий админ AD и ненастоящий программист
    //...declarations and initializations omitted
               do
               {
                   //...some code omitted
                   if (j != i)
                   {
                       swap(i, j);
                       i = j; 
                   }
               } while (j != i);

    Не работает, потому что вы сначала присваете j значение i, если они не равны, а потом, в условии продолжения цикла, сравниваете их значения. Естественно, они будут равны и выход их цикла получится на первой же итерации. Проверять i==j как условие выхода из цикла надо чуть раньше, например, так:
    //...declarations and initializations omitted
               do
               {
                   //...some code omitted
                   if (j != i)
                   {
                       swap(i, j);
                       i = j; 
                   }
                   else break;
               } while (true);


    Ну, а что до второго вопроса, то в .NET, начиная с 6.0 есть класс System.Collections.Generic.PriorityQueue<TElement,...
    Ответ написан
    6 комментариев
  • Как найти минимальное число прохождений по автомату до конечного состояния с N вероятностью?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Есть простой трюк сильно упростить задачу: Измените переходы из "конечной" вершины - она теперь с вероятностью 100% будет вести только в саму себя. Таким образом, процесс хотя бы раз достигший вершины, навсегда в ней останется.

    А вопрос из задачи (если его понимать как: минимальное количество шагов, чтобы хотя бы раз посетить конечную вершину с вероятностью >99%) становится эквивалентен: минимальное количество шагов, чтобы быть в конечной вершине с вероятностью не меньше 99%.

    А тут уже надо найти минимальное число k, такое что соответствующее значение в матрице A^k было бы > 0.99. A тут - это матрица переходов.

    Можно или в тупую умножать матрицу саму на себя, пока значение в строке начальной вершины и столбце конечной вершины не станет достаточно большим. Это будет O(N^3*ответ). Или можно делать хитро: бинарным поиском перебирайте степень, а внутри логарифмическим возведением в степень считайте A^k. Это будет O(N^3*log(ответ)^2).
    Ответ написан
    Комментировать
  • Как реализовать виртуальный кеш, tlb?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    как реализованы в kvm qemu virtualbox бош и другие

    В KVM -- никак, KVM использует фичу хостового процессора известную как 2-stage translation, при этом на первой стадии хостовый процессор выполняет трансляцию гостевого виртуального адреса в гостевой физический, аппаратно.

    В QEMU -- я тебе уже писал как, с деталями и ссылочками в код. Но ты вместо того чтобы задавать конкретные вопросы опять начинаешь говорить что там всё сложно и непонятно.

    Какой там алгоритм замещения(Или его там нету).

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

    void* translate(int acid, int addr){

    Похож на реализацию собственного TLB QEMU, только там нет ASID и в качестве тега используются все биты виртуального адреса кроме младших (обычно младших 12, но может быть меньше, если у эмулируемой архитектуры есть страницы меньшего размера).
    Ответ написан
    Комментировать
  • Чем загрузчик в виртуальных процессорах отличается от реального? Какой жизненный цикл запущенной ОС на виртулальном?

    Melkij
    @Melkij
    PostgreSQL DBA
    Запуститься ли обычная ос на виртуальном процессоре(не понимаю как это протестировать. так как образы ос для виртуалок, чет немного другие, а что в них другого в этом вопрос)

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

    Точно не все, к примеру в qemu память выделяется динамически. А значит. Ram может расти. А в реальности, я не могу взять и RAM увеличить в 2 раза по команде. Значит есть инструкция, new которая берет и из неоткуда(с точки зрения вирт ос) берет память.

    https://en.wikipedia.org/wiki/Memory_ballooning
    Ядро гостевой ОС намеренно модифицировано и знает как попросить больше памяти у гипервизора.

    То что вы упускаете: виртуального процессора не существует.
    Управление памятью же... Хе-хе. Если не сильно ошибусь в исторический экскурс, то в прошлом году исполнилось уже 50 лет с тех пор как память в x86 перестала работать так наивно, как вы описали. https://en.wikipedia.org/wiki/Virtual_memory
    malloc гигабайтного куска памяти уже очень давно не даёт гигабайтный кусок непрерывных адресов в физической RAM. Фактически, malloc сейчас вообще не даёт память, а только обещает её дать позже. Куда и как эта память будет распределена по физической RAM - да фиг его знает, этим управляет операционная система. Виртуализация соответственно возводит сложность управления виртуальной памятью в квадрат. Это может быть как двойная работа - сначала гость в том что считает своей RAM распихивает всё что есть как нравится, затем гипервизор ничего не зная о алгоритмах управления памятью в госте распихивает занимаемую гостем память по своей виртуальной памяти. Или это может быть какая-то кооперация.
    Ответ написан
    Комментировать
  • Чем загрузчик в виртуальных процессорах отличается от реального? Какой жизненный цикл запущенной ОС на виртулальном?

    gbg
    @gbg
    Любые ответы на любые вопросы
    на виртуальном процессоре

    1. Современные системы виртуализации используют реальный процессор. Есть конечно и системы, которые эмулируют процессор программно, но это когда речь идет об эмуляции между архитектурами - например, код для ARM запускают на x86.
    2.
    так как образы ос для виртуалок, чет немного другие, а что в них другого в этом вопрос

    отличия в драйверах. "Обычная" ОС должна работать в виртуализации без проблем.
    3.
    А значит. Ram может расти.

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

    Для современного процессора, выполнение гостевой ОС - это выполнение обычной программы, просто в какие-то моменты он перехватывает обращения к железу и подсовывает туда код гипервизора. Если же мы говорим о программной реализации процессора, то памятью может быть просто массив байтиков.
    Ответ написан
    Комментировать
  • Почему в с# в стуктурах с static void* ptr указателем этот указтаель не равен нулю при инициализации?

    vabka
    @vabka Куратор тега C#
    Токсичный шарпист
    // в откладке показывает TRUE, но как-будто false отрбатывает

    Предположу, что это просто глюк дебаггера. У меня он вообще не может прочитать значение Ptr и пишет вот что:

    Failed to read static field: Статическая переменная недоступна, поскольку еще не инициализирована. (Исключение из HRESULT: 0x8013131A). The error code is CORDBG_E_STATIC_VAR_NOT_AVAILABLE, or 0x8013131A.

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

    Но если попытаться вывести в консоль значение Ptr, то будет 0:
    unsafe {
      void* x = null; // Можно выводить и Env.Ptr - будет тот же результат
      Console.WriteLine((nint)x); // 0
    }
    Ответ написан
    Комментировать
  • Как в архитектурах risc одинаковые виртуальные адреса разных контекстов задач различаются?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    В risc вроде там куча csr регистров

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

    на разных компиляторах одна си операция ассемблируется то в комбинацию lui + addi, то в комбинацию auipc +addi

    Ты указал ARM в тегах, но у ARM нет инструкций lui и auipc. Такие инструкции есть у RISC-V.
    Если ты посмотришь в The RISC-V Instruction Set Manual, раздел 2.4 Integer Computational Instructions, то увидишь, что опкод lui загружает константу собранную из 20 битов непосредственного значения из инструкции и 12 нулевых младших битов в целевой регистр, а auipc прибавляет такую же точно константу к PC и загружает в целевой регистр результат сложения, и в этом вся разница между ними.

    где какая используется не совсем понимаю.

    lui используется для генерации констант, которые не зависят от того, где расположен код, а auipc для генерации констант, которые двигаются вместе с кодом. Т.е. Если ты хочешь вызвать функцию, которая находится дальше чем ±2К от точки вызова, ты можешь сгенерировать её адрес инструкцией auipc, и полученный код будет работать одинаково, независимо от того, по какому адресу он будет размещён. А если тебе надо поместить в регистр константу, например 0x12345678, то ты можешь это сделать парой инструкций lui rd, 0x12345 ; addi rd, rd, 0x678 и значение константы будет всегда одинаковым, вне зависимости от того, где будет этот код.

    Каким образом одинаковые адреса различаются. Или они просто не могут быть одинаковыми(типа ос позаботиться)?

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

    Как они в tlb обрабатываются, если вдруг они реально могут быть одинаковыми, и там нету ни каких дополнительных индексов процесса)

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

    У ARM есть регистры TTBR с примерно той же функцией, что и cr3 в x86.
    У RISC-V есть CSR satp, содержащий ASID и базовый адрес корневого каталога страничных таблиц. Об этом можно прочитать в разделе 4.1.12 Supervisor Address Translation and Protection (satp) Register спецификации The RISC-V Instruction Set Manual Volume II: Privi....
    Ответ написан
    Комментировать