リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
ITスキルロードマップ roadmap.sh がすごい。AI and Data Scientist について対応する本をまとめた - Qiita
ITスキルロードマップ roadmap.sh がすごい。AI and Data Scientist について対応する本をまとめた機械学習データ分析キャリアデータサイエンスデータサイエンティスト Developer Roadmapsというサイトがすごいです。ITエンジニアの分野別にスキルアップのロードマップが示されています。 言語、基盤、アプリ、かなり網羅されています。 その中のAI and Data Scientist Roadmapについての推薦図書まとめです。 雑感 これだけ学んでいれば「こいつ知ってるな」感がありますね。ただ気になる点としては ビジネス、ドメイン知識や分析目的定義などのスキルについて言及がないのは残念。 いきなり数学から入るコースになってますが、一旦は飛ばしてコード写経してから戻ってきても良いと思います。ここで挫折すると勿体無いので。 計量経済学重視の観点はいいですね
法律のデータ構造と検索
デジタル庁は、法令標準 XML スキーマに準拠した、現行の法令データをe-Gov法令検索というサイト上で公開しています[1]。今回、この法令XMLをパースするPythonライブラリ ja-law-parser をつくり、法令データの全文検索をしてみました。 この記事では、日本の法令とそのデータ構造、法令XMLパーサについて解説し、最後に、それらを使った法令データの全文検索システムを実装する方法をご紹介します。法令検索の実装についても、GitHubリポジトリで公開しています。 この記事は、情報検索・検索技術 Advent Calendar 2023の16日目の記事です。 法律と法令 法律とは 法律の制定と公布 法律と法令の違い 法律の改正 法令のデータ構造 e-Govの法令データ 法令標準XMLスキーマ 法令番号と法令ID 題名 本則と附則 条・項・号 編・章・節・款・目 法令XMLパーサ：
At Buildkite, we've historically stored our data with two keys. We use sequential primary keys for efficient indexing, and UUID secondary keys for external use. The upcoming UUIDv7 standard offers the best of both worlds; its time-ordered UUID primary keys can be utilized for indexing and external use. This blog post will take you on the journey Buildkite took that led to our eventual adoption of
This post is about why we need a coroutine package for Go, and what it would look like. But first, what are coroutines? Every programmer today is familiar with function calls (subroutines): F calls G, which stops F and runs G. G does its work, potentially calling and waiting for other functions, and eventually returns. When G returns, G is gone and F continues running. In this pattern, only one fu
Matthias Endler - Consultant at Corrode.dev • 27 September 2023 Oh no, not another 'Is Rust better than Go?' article. Seriously, haven't we all had our fill of these comparisons by now? But before you sigh in exasperation, hear us out! Many comparisons between Go and Rust emphasize their differences in syntax and the initial learning curve. However, ultimately, what matters is the ease of use for
50 Shades of Go: Traps, Gotchas, and Common Mistakes for New Golang Devs
50 Shades of Go: Traps, Gotchas, and Common Mistakes for New Golang Devs 50 Shades of Go in Other Languages Chinese Translation: blog post, segmentfault (by wuYin) - needs updates Another Chinese Translation: blog post (by Shadowwind LEY) - needs updates Russian Translation: blog post (by Ilia Ozhereliev, Mail.Ru Group Blog) - needs updates Overview Go is a simple and fun language, but, like any o
February 05, 2024 · 26 mins · 4728 words Discussion on HackerNews. Last September I hopped on board with Wallapop as a Search Data Scientist and since then part of my work has been working with Solr, an open source search engine based on Lucene. I’ve got the basics of how a search engine works, but I had this itch to understand it even better. So, I rolled up my sleeves and decided to build one fr
Why SQLite Uses Bytecode
1. Introduction Every SQL database engine works in roughly the same way: It first translates the input SQL text into a "prepared statement". Then it "executes" the prepared statement to generate a result. A prepared statement is an object that represents the steps needed to accomplish the input SQL. Or, to think of it in another way, the prepared statement is the SQL statement translated into a fo
LogLog Games
The article is also available in Chinese. Disclaimer: This post is a very long collection of thoughts and problems I've had over the years, and also addresses some of the arguments I've been repeatedly told. This post expresses my opinion the has been formed over using Rust for gamedev for many thousands of hours over many years, and multiple finished games. This isn't meant to brag or indicate su
The problem with using a UUID primary key in MySQL — PlanetScale
Universally Unique Identifiers, also known as UUIDs, are designed to allow developers to generate unique IDs in a way that guarantees uniqueness without knowledge of other systems. These are especially useful in a distributed architecture, where you have a number of systems and databases responsible for creating records. You might think that using UUIDs as a primary key in a database is a great id
WEELメディア事業部LLMリサーチャーの中田です。 ここ数日で、言語生成AIの「Groq」が話題になりました。 これにより、GPTよりも高速でテキストを生成できるんです、、、！ "GPT-3.5 class LLMs are too slow." Sure, that was true last week. Here is Groq (not the same as Musk's Grok) running Llama 2. Watch for the moment I click send. If you want to try: https://t.co/aZKkWVsamS pic.twitter.com/gOlB4cL5MC — Ethan Mollick (@emollick) February 19, 2024 XでのGroq関連の投稿のいいね数は、すで1100を超えており、
Introduction⌗ Postgres queue tech is a thing of beauty, but far from mainstream. Its relative obscurity is partially attributable to the cargo cult of “scale”. The scalability cult has decreed that there are several queue technologies with greater “scalability” than Postgres, and for that reason alone, Postgres isn’t suitably scalable for anyone’s queuing needs. The cult of scalability would rathe
An interface is not an interface - Recent thoughts about clean coding - spacelyのブログ
Introduction Recently I've had to work on code which seemed to be based on clean architecture, but after a while I concluded that it is probably not and it made me think about clean coding in general and the principles of clean architecture in particular. Is it about a set of rules, and we are guaranteed to achieve cleanness as long as we follow them? Or is it about abstract principles, which we c
Biome v1.6
In this release, we’re happy to provide partial support for Astro, Svelte and Vue files. What does partial support mean? While the team is working on a unified data structure for HTML-ish languages, we discovered that we could provide Biome functionalities to those files with just a few changes, albeit with some limitations. This means that Biome is able to analyze the JavaScript/TypeScript portio
Back to articlesOnyx, a new programming language powered by WebAssemblyLearn about Onyx, a new imperative programming language that leverages WebAssembly and Wasmer for seamless cross-platform support What is Onyx? Onyx is a new programming language featuring a modern, expressive syntax, strict type safety, blazingly-fast build times, and out-of-the-box cross platform support thanks to WebAssembly
エアプにならないために、実際に moonbit を使ってコードを書いてみた感想を書く。 JSON Parser を書いた パッケージレジストリである https://mooncakes.io を見た限り、使いやすい json parser がなさそうなので、とりあえず自分用のをでっち上げた。 mooncakes.io に publish してあるので、 moon add mizchi/json で使える。品質が良くなくても ネームスペース付きで publish するので別に邪魔にならない気がした。 なんで作ったかというと、公式 example の cloudflare workers の example は単純なフィボナッチを計算するだけで、構造的なデータを返すことができない。 moonbit と js 間の文字列の受け渡しについては、あとで別の記事を書く。 使い方 fn main { l
AST vs. Bytecode: Interpreters in the Age of Meta-Compilation
233 AST vs. Bytecode: Interpreters in the Age of Meta-Compilation OCTAVE LAROSE, University of Kent, UK SOPHIE KALEBA, University of Kent, UK HUMPHREY BURCHELL, University of Kent, UK STEFAN MARR, University of Kent, UK Thanks to partial evaluation and meta-tracing, it became practical to build language implementations that reach state-of-the-art peak performance by implementing only an interprete
Preparing for the Systems Design and Coding Interview
At Big Tech and high-growth startups, coding and systems design interviews are common - and fairly standard. A lot of people have asked me for preparation advice for these. Here is what I used when getting ready for an E5/E6 Facebook interview, and the one at Uber - where I was hired as a senior software engineer (L5). It's the same resources I recommend to people who are preparing for Big Tech or
This blog tries to summarize all the choices and paths you could take to implement your next programming language, more specifically the frontend for your language. There are a lot of factors that will influence your choices. Maybe you have your favorite host language that you would like to use for implementing your language, whether your language is dynamically or statically typed, or you are des
A decision that arises over and over when designing concurrent programs is whether to represent program state in control flow or as data. This post is about what that decision means and how to approach it. Done well, taking program state stored in data and storing it instead in control flow can make programs much clearer and more maintainable than they otherwise would be. Before saying much more,
Collaboratively editing strings of text is a common desire in peer-to-peer applications. For example, a note-taking app might represent each document as a single collaboratively-edited string of text. The algorithm presented here is one way to do this. It comes from a family of algorithms called CRDTs, which I will not describe here. It's similar to the approaches taken by popular collaborative te
I thought it would be fun to go outside of my comfort zone of web development topics and write about something completely different and new, something I have never written about before. So today, I'm going to show you how to implement a programming language! The project will parse and execute programs written in a simple language I called my (I know it's a lame name, but hey, it is "my" language).
We've finished porting Turborepo, the high performance JavaScript and TypeScript build system, from Go to Rust. This lays the groundwork for better performance, improved stability, and powerful new features. Here’s how we finished this port and shipped the first all-Rust version of turbo. Since last timeAt the end of our previous article, we had completed the “Rust-Go-Rust sandwich”, or “Go sandwi
For this second post in Zed Decoded, our blog & video series in which we're taking a closer look at how Zed is built, I've talked to Zed's three co-founders — Nathan, Max, Antonio — about the data structure at the heart of Zed: the rope. Companion Video: Rope & SumTree This post comes with a 1hr companion video, in which Thorsten, Nathan, Antonio, and Max use Zed to look at how Zed uses the Rope a
Across these repos, the savings average around 75%, but memory reductions are non-linear: as projects get larger, so does the relative decrease in memory usage. We’ll explain this in more detail below. Gopls and the evolving Go ecosystem Gopls provides language-agnostic editors with IDE-like features such as auto-completion, formatting, cross-references, and refactoring. Since its beginnings in 20
SIEVE: an Efficient Turn-Key Eviction Algorithm for Web Caches - SIEVE is simpler than LRU
SIEVE is simpler than LRU¶ Caching is a method of storing temporary data for quick access to keep the online world running smoothly. But with limited space comes a critical decision: what to keep and discard. This is where eviction algorithms come into play. Our team recently designed a new cache eviction algorithm called SIEVE: it is very effective and simple with just one queue. Website Paper Up
Flaky Tests In React: Detection, Prevention and Tools - Semaphore
In the context of React, testing is a non-negotiable process to maintain code quality and a smooth user experience. However, there’s one frustrating bad news that is commonly faced when running tests in React. And that is flaky tests. In the simplest of words, flaky tests are tests that seem to pass most of the time but fail sometimes, all without changes to the code or test — just for no reason.
My wife and I decided to make an 8-bit, top-down, Zelda-like game written for the PPU466 (from CMU 15-466 Computer Game Programming course). The PPU466 is a graphics API kind of like the PICO-8 fantasy console, in the sense that it’s restricted to 8-bit graphics, 4 colors per tile, fixed backgrounds, and a low number of sprites. As a part of the game, I wanted our monsters to chase the player. So
Text editors can be an interesting challenge to program. The types of problems that text editors need to solve can range from trivial to mind-bogglingly difficult. Recently, I have been on something of a spiritual journey to rework some internal data structures in an editor I have been building, specifically the most fundamental data structure to any text editor: the text. Table of Contents Resour
Using localStorage in Modern Applications: A Comprehensive Guide When it comes to client-side storage in web applications, the localStorage API stands out as a simple and widely supported solution. It allows developers to store key-value pairs directly in a user's browser. In this article, we will explore the various aspects of the localStorage API, its advantages, limitations, and alternative sto
Originally we implemented a feature to persist an event-stream into DynamoDB to allow customers to retrieve them. This proved effective, serving as a strong use case for a key/value storage, yet the drawback was its high cost. Moving to provisioned billing-mode reduced cost by ~50%, but that was not going to be sustainable as we scaled to more customers. We also kept multiplying the cost each time
Logic programming in Rust
use ascent::ascent; ascent! { relation edge(i32, i32); relation path(i32, i32); path(x, y) <-- edge(x, y); path(x, z) <-- edge(x, y), path(y, z); } fn main() { let mut prog = AscentProgram::default(); prog.edge = vec![(1, 2), (2, 3)]; prog.run(); println!("path: {:?}", prog.path); } Features Lattices Ascent supports computing fixed points of user-defined lattices. The lattice keyword defines a lat
1. One man’s constant is another man’s variable. 2. Functions delay binding; data structures induce binding. Moral: Structure data late in the programming process. 3. Syntactic sugar causes cancer of the semicolon. 4. Every program is a part of some other program and rarely fits. 5. If a program manipulates a large amount of data, it does so in a small number of ways. 6. Symmetry is a complexity-r
This week I found myself digging through the code of c4, an implementation of C “in four functions”, by Robert Swierczek. I remember coming across c4 when it was released ten years ago. It got me excited: hey, C in four functions, that means it’s easy to understand right? That excitement turned into “oh, I see” as soon as I scrolled through the code. c4 is dense, barely commented, and, frankly, st
Amazon MemoryDB for Redisの論文がSIGMOD 2024で採択されたので読んでみた | DevelopersIO
Amazon MemoryDBではトランザクションログサービスへの耐久性のオフロード、スナップショット用にephemeralクラスタを作成、形式手法(TLA+)で一貫性の検証などが活躍しています Amazon MemoryDB for RedisはAWSが2021年から提供するRedis互換でありながら高速なパフォーマンスと耐久性を兼ね備えたエンタープライズなインメモリデータベースです。このAmazon MemoryDBの仕組みについて説明した論文が、2024年6月にチリ・サンティアゴで開催される国際的なデータベース学会の「SIGMOD/PODS 2024」で採択されました。 The 2024 ACM SIGMOD/PODS Conference: Santiago, Chile - Welcome Amazon MemoryDB: A fast and durable memory-fi
AWK As A Major Systems Programming Language — Revisited Preface I started this paper in 2013, and in 2015 sent it out for review to the people listed later on. After incorporating comments, I sent it to Rik Farrow, the editor of the USENIX magazine ;login: to see if he would publish it. He declined to do so, for reasonably good reasons. The paper languished, forgotten, until early 2018 when I came
In this blog, I am going to explain the important concepts of Heap and use the ptmalloc in the Glibc 2.31 library as an example. The heap is a beautiful mess :) I really like the saying shown above. The word Heap we always use refers to the dynamically allocated segment in the virtual memory space of a process, but it actually stands for the implementation of the memory pool(the dynamic memory all
Writing a scheduler for Linux in Rust that runs in user-space
Overview I’ve decided to start a series of blog posts to cover some details about scx_rustland, my little Linux scheduler written in Rust that runs in user-space. This project started for fun over the Christmas break, mostly because I wanted to learn more about sched-ext and I also needed some motivation to keep practicing Rust (that I’m still learning). In this series of articles I would like to
This is my closing talk (video) from the GopherConAU conference in Sydney, given November 10, 2023, the 14th anniversary of Go being launched as an open source project. The text is interspersed with the slides used in the presentation. What We Got Right, What We Got Wrong INTRODUCTION Hello. Let me start by thanking Katie and Chewy for the giving me the honor of presenting the closing talk for the
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
徐々に高度になるリングバッファの話 - Software Transactional Memo
Goodbye to sequential integers, hello UUIDv7!
research!rsc: Coroutines for Go
Rust Vs Go: A Hands-On Comparison
A search engine in 80 lines of Python
【Groq】一秒で500トークン、GPT-4の25倍のスピードで出力できるAIを使ってみた | WEEL
Choose Postgres queue technology
Onyx, a new programming language powered by WebAssembly
moonbit で json パーサーを書いてみた 感想
The path to implementing a programming language
research!rsc: Storing Data in Control Flow
CRDT: Text Buffer - Made by Evan
Building a Toy Programming Language in Python
Finishing Turborepo's migration from Go to Rust – Vercel
Zed Decoded: Rope & SumTree - Zed Blog
Scaling gopls for the growing Go ecosystem - The Go Programming Language
A* Tricks for Videogame Path Finding | Tim Mastny
Text Editor Data Structures
Using localStorage in Modern Applications - A Comprehensive Guide | RxDB - JavaScript Database
Moving from DynamoDB to tiered storage with MySQL+S3
Epigrams in Programming | Computer Science
Exploring the c4... compiler?
AWK As A Major Systems Programming Language — Revisited
Understanding the Heap - a beautiful mess
What We Got Right, What We Got Wrong