r/computerscience

Reqflow : pick an architecture (WhatsApp,
Uber, Netflix…), hit play, watch a request flow through it step by step. Click any component for purpose + tradeoffs. Kill the cache and watch the path change.

15 systems, 18 concept guides, a drag-and-drop Builder with AI review, and a timed Interview mode.

Feedback welcome — especially what's missing from the 15.

Hi, I successfully passed exams such as Calculus, Real Analysis, Abstract Algebra, Linear Algebra and Physics which are all tough subjects but in my personal opinion not as tough as Theoretical Computer Science.

Even though I understand the proofs that are presented in a mathematical way, I fail to connect the dots. For example there can't be a program enumerating all the total computable functions. The proof is quite easy (it uses the diagonalization method) but I feel like "I am not convinced" by the proof. Neither this one nor others. I can not fully grasp why I am not "convinced" by them: maybe it's the overlap between the mathematical world and the real world, maybe because it mixes few concepts that to me feel "disconnected" or maybe because I feel I am missing something deep.

For the matter the course is called "Introduction to Theoretical Computer Science" so I guess I am not required to understand concepts at a very deep level, but I would really like to, despite not able to.

Has anyone ever had similar problems?

I'm continuing the research on semantics for a new language. After studying Mutable Value Semantics (MVS) in the first post (reddit discussion), I wrote a follow-up that examines the trade-offs between MVS and the Ownership & Borrowing model.

The post covers:

• Friction points in Rust's borrow checker
• Where Hylo's MVS solves them and where it introduces new trade-offs
• Swift's hybrid approach and its runtime exclusivity checks
• Open questions I'm exploring for my own language design

I'd love to hear your thoughts.

Link: https://federicobruzzone.github.io/posts/eter/MVS-or-ownership&borrowing.html

I just released citor, a small header-only C++20 thread pool / parallel runtime aimed at CPU-bound workloads where per-dispatch latency actually shows up in the profile.

Repo: https://github.com/Lallapallooza/citor

The main idea is: keep the common CPU-parallel shapes in one pool, avoid per-call allocations on the hot path, let the producer participate as slot 0, and make short repeated phases cheaper than repeatedly waking a worker team.

The simplest thing looks like what you'd expect:

citor::ThreadPool pool(8);

pool.parallelFor<citor::HintsDefaults>(
    0, data.size(),
    [&](std::size_t lo, std::size_t hi) {
        for (std::size_t i = lo; i < hi; ++i)
            data[i] *= 2;
    });

Beyond parallelFor, it has deterministic parallelReduce, parallelScan, parallelChain, runPlex for repeated phases over the same partition, recursive forkJoin with per-worker Chase-Lev deques, bulkForQueries, and submitDetached. There is also a PoolGroup that creates one arena per shared-L3 group, mostly useful on multi-CCD Zen.

A few internals that ended up mattering more than I expected:

• each worker owns a cache-line-aligned mailbox and the whole dispatch protocol is a per-slot mailbox stamp, no shared queue
• the producer can short-circuit small jobs by CAS-ing the worker's mailbox to DONE itself and running the body inline, no wake at all (worker's own ack races the producer's self-stamp, loser short-circuits);
• the join barrier is a per-slot done-epoch scan with cancellation riding the same epoch read, so no shared sense bit and no per-iteration cancel poll
• the worker's spin-entry rdtscp doubles as a store-buffer drain, so the producer sees the DONE stamp before its next mailbox read - free side benefit of timing the spin
• kCacheLine is 128 bytes rather than 64 because Zen prefetches in cache-line pairs and contended atomics get measurably worse if you size to 64.

For perf, I wrote a comparative harness against BS::thread_pool, dp::thread_pool, task-thread-pool, riften, oneTBB, Taskflow, Eigen, OpenMP, Leopard, dispenso, libfork, and TooManyCooks. Competitor revisions are pinned, host gates are printed at startup, OpenMP wait policy is normalized, and raw samples can be exported as JSON.

In my current benchmark sweep, citor wins roughly:

• 92% of contested cells on a Ryzen 9950X3D
• 75% on a 96-core Genoa box
• 69% on a 48-core Sapphire Rapids box

Hot fan-out dispatch on the 9950X3D is usually in the 100-400 ns range depending on participant count and shape.

Please treat those as "my harness on my machines or aws," not universal truth. If the numbers matter to your use case, run the benchmark yourself. The README has the methodology and reproduction commands.

There is real work left:

• topology detection is still shaped mostly around Zen CCDs
• multi-socket EPYC, sub-NUMA clustering, hybrid P/E cores, and Intel mesh are not first-class yet
• parallelReduce uses static contiguous chunks and does not steal after a worker finishes, so heavy-tail bodies can leave cores idle
• the coroutine wrapper queues on a per-pool driver thread rather than doing continuation stealing
• bulkForQueries only fans across queries today a true 2D fan is probably the next useful shape.

What citor is not:

• not an I/O executor
• not a general async/future abstraction
• not a TBB or OpenMP replacement for arbitrary workloads
• not tuned equally for every CPU topology

I'd especially like feedback on benchmark fairness, API shape before 1.0, missing competitors, and whether the affinity / pinning behavior is too surprising for a library like this and for sure any perf improvenments suggestions. If anything in the README reads like overclaiming, I'd rather fix it now.

upd. There is an external benchmark as well https://github.com/tzcnt/runtime-benchmarks

Всем привет, я пишу здесь об этом так как не знаю что добавить. Я делаю собственное ядро на VoidLang основанном на C++, но оно немного кривое, пока что работоспособных прототипов нет (кроме Linux дистрибутива созданного мной 2 месяца назад, в самом начале проекта основанного на спор), вот некоторые изменения файловой системы:

.vx (ранее .void, это исполняемые файлы по типу .exe)
.vkr (новые файлы, модули ядра)
.vsec (системы безопасности)
.vdat (контейнеры данных вместо .vd)
.varc (ранее .xsr, разница в том что новые не сжимают файлы, как можно понять является архивом)
.vcfg (файл конфиги)
.vme (ранее .vud, файл пользователя)
.vsav (файл сохранений)
.vth (файл темы)
.vlog (файл для логов системы и приложений)
.vfn (файл для шрифта)
.vsh (скрипты)
.vai (файл для ИИ модулей на будущее)

Могу ответить на некоторые вопросы как смогу, но не обещаю что буду отвечать часто, в регионе отключают интернет.

I want a comparison sort where the human does the comparison (so all other operations take essentially 0 time relatively). I have 900 things to sort (I'm ranking shows I've watched), so binary comparisons would take a long time (~7541 comparisons). If we instead use k-ary comparisons (computer shows me k=10 at a time and I rank each batch individually), then, theoretically, we could get down to only log(900!)/log(10!)=~347 10-way comparisons!

I've looked around, but there doesn't seem to be much research on the topic. So I thought of a simple idea: just do binary insertion sort, but include other, unsorted elements in each comparison as well. That way, when we later go on to insert those unsorted elements, we already have a bit of an idea of the range they can be inserted in.

You can see a demonstration of my idea for k=3 in this video: https://x.com/JentGent/status/2056809963625078974

(I tried to insert them in alphabetical order to make the demonstration clearer, but I accidentally went out of order for some of the items.)

Here's a sketch of how the algorithm would work:

1. Sort the first k items using one k-sort, remove them from the `unsorted` list, and place them in the `sorted` list. Update our DAG according to the k-sort (add k-1 directed edges)
2. For each element A in the unsorted list:
   1. Calculate `low` and `high` from our DAG using DFS. At first, `low` will just be 0 and `high` will just be `sorted.length`---a typical binary search. In general, as we update our DAG, `low` is the lowest index of `sorted` from which DFS fails to find A (in increasing direction), and `high` will be similar, but backwards, from the end of `sorted`.
   2. While low < high:
      1. Set `mid` to `(low + high) // 2`
      2. Choose k-2 extra elements from `unsorted` to include in our k-sort (via a greedy independent sets algorithm on our DAG)
      3. k-sort all of A, `sorted[mid]`, and our k-2 extra elements
      4. If A appears after mid in the sort, set `low` to `mid+1`; otherwise, set `high` to `mid`
      5. Update our DAG according to the k-sort
   3. Insert A into `sorted` at index `low` and remove A from `unsorted`

How would you implement this in practice? Right now, I'm updating the whole directed graph with a DFS on every node for each comparison, which I guess is fine if I say all operations except comparison take negligible time, but there's surely a more elegant solution. I've also faced some interesting edge cases that might complicate an implementation. Ideally, you should never know beforehand the order of any two pairs of elements in any k-way comparison you make, but it seems that's sometimes not possible

EDIT: it seems this algorithm as it is only gets us down to ~2x the lower bound. maybe there's a better way to choose the k-2 extra elements? I'm also considering an equivalent of quicksort where you set the pivot as the midpoint of a k-sort ...

Hey, I'm interested in the concept of Reverse Engineering, I know very basic coding in python and c++. So how to learn this thing? The tutorial seems very hard and I've been stuck for the past 4-5 months. Need advice on this

https://preview.redd.it/pxxfgcb2j22h1.jpg?width=1320&format=pjpg&auto=webp&s=ab31d62b485a4d613b2681b0551000d3750519fa

Just saw this image on Reddit.

Do you think it'll actually happen, or will competitors just undercut and lower prices, i hope second will happen

Does anyone know what centralized traffic engineering is? I can’t seem to find much information about it. There’s very little information discussing this topic.

Gng im so confused bw cse and ece...

What should I do? I looked into ece and found it good but I dont wanna regret my choice.

Cse on the other hand coding and all I find kinda boring but tbh i grew up playing games on laptop learning excell sheets and all.

I heard ECE students can also go in software side later if they don't like it.

That's why im considering ECE.

Someone pls help 🙏 🙏 🙏

I’m 33 years old and I’ve been programming for almost 20 years. I learned programming with C++, and I used it consistently until I was 25. Nowadays I’m a backend developer in a company where I mainly work with .NET and Golang.

Question:
I recently started reading Computer Systems: A Programmer’s Perspective and I’m currently at the first chapter. While it seems comprehensive and interesting, I’m not sure it’s exactly what I’m looking for.

What I would like is something that simply teaches me how the various parts of an operating system work, so I can start exploring it and have some fun with it.

I already understand concepts such as why contiguous memory layouts matter, or why structuring data one way can be preferable to another. And while I’m sure this book could still teach me a lot, I’d like to stay focused specifically on operating systems.

So, is this the right book for my situation and goals, or is there something better suited to what I’m looking for?

Thanks for your attention, and have a great day.

Thoughts?

Apologies if this is a silly question, my linear algebra is rusty and my knowledge of grammars is only that required for an undergrad compilers course.

In Aho and Ullman's "Theory of Compiling" book, the authors use a very suggestive notation in chapter 2.2, where they discuss finding regular expressions that satisfy some set of equations. They even note that the algorithm to solve such set of equations is "reminiscent of solving linear equations using Gaussian elimination".

Another thing that feels vaguely similar is this concept of "generation". In the same way that vector spaces are generated from some basis, and the behavior of a linear transformation is determined by how it acts on the basis, a "nice" language is generated by some finite list of production rules, and once a set of production rules are found we can presumably tell a fair bit about the language it generates.

An immediate flaw that comes to mind with the above analogy is how "useless" generators are handled in linear algebra vs. formal grammars. Recall that if we have a generating set for a vector space, we have "useless" vectors that we can trim away to eventually find a linearly independent basis for that space. To my understanding, there is an analogous process to trim useless rules from a grammar that preserves the language it generates. However, if we have a context free grammar for a regular language, it isn't clear to me that there is a generic way to turn that context free grammar into a simpler regular grammar, which means that the amount of simplification we can do is limited if thats correct.

Is there anything deeper here? Or am I grasping for straws and any similarities are superficial?

I am little confused on what these languages are really doing or what their purpose is. I have done research but still want to make sure I have a very deep understanding on whats actually happening. From my knowledge, Angular is you logic, routing, etc. It's just TypeScript which I'm familiar with. Now Ionic provides a UI-toolkit to use for your tags to easily convert to a mobile environment or mobile web app? And Capacitor is what actually does the conversion? I am confused on what it actually does because I saw something that said its not actually a native mobile app, it just allows access to native mobile tools like the camera. Just overall confused and would love for some clarification, maybe use examples like Dart and flutter?

Question for people working with LLMs / RAG:

If a model sees text in its context window, how do we make sure it knows whether that text is actually valid evidence?

Ex: prompt might include current docs, old docs, retrieved snippets, answer choices, and injected text. All of that is “context,” but not all of it should count as evidence.

You think it’s mainly a RAG/provenance problem, or prompt-injection problem, or just something we need better evals for?

I’m thinking of this as a source-boundary failure, as though the model treats text as evidence just because it is present.