Hacker News Reader

nitelyon Finding all regex matches has always been O(n²)

It's similar to RE2, but it lacks the on the fly DFA, ie: it's just the classic Thompson's NFA with some tweaks. It does not implement find all the same way, though.

nitelyon Finding all regex matches has always been O(n²)

FWIW, nim-regex does achieve linear time in the rebar test[0], even if the regex includes capture groups. It's NFA based.

[0]: https://github.com/BurntSushi/rebar/pull/20#issuecomment-256...

nitelyon A critical look at MCP

Yes, and the client may do multiple requests, and if all take long to be processed you may end up with a lot of open connections at the same time (at least on http1), so there is a point to fast HTTP requests+SSE, instead of slow requests (and no SSE). Granted, if the server is HTTP2 the requests can share the same connection, but then it'd be similar to just using WS for this usage. Also, this allows to queue the work, and processed it either sequentially or concurrently.

By async I meant a process that may take longer than you are willing to do within the request/response cycle, not necessarily async IO.

nitelyon A critical look at MCP

> What benefit is SSE providing here? Let the client decide when a session starts/ends by generating IDs and let the server maintain that session internally.

The response is generated asynchronously, instead of within the HTTP request/response cycle, and sent over SSE later. But emulating WS with HTTP requests+SSE seems very iffy, indeed.

nitelyon You might not need WebSockets

not if you need bidirectional communication, for example a ping-pong of request/response. That is solved with WS, but hard to do with SSE+requests. The client requests may not even hit the same SSE server depending on your setup. There are workarounds obviously, but it complicates things.

nitelyon There isn't much point to HTTP/2 past the load balancer

There is a gem that implements lightweight threads[0], and there is an HTTP/2 server that seems to abstract things out[1]. Your point probably still holds in the context of ruby + async + http/2; but then it's not http/2 fault, but rather ruby for not having a better concurrency story, like say golang.

[0]: https://github.com/socketry/async

[1]: https://github.com/socketry/falcon

nitelyon There isn't much point to HTTP/2 past the load balancer

In reality you would build your application server on top of the HTTP/2 server, so you'd not have to deal with multiplexing, the server will hide that from you, so it's the same as an HTTP/1 server (ex: you pass some callback that gets called to handle the request). If you implement HTTP/2 from scratch, multiplexing is not even the most complex part... It's rather the sum of all parts: HPACK, flow-control, stream state, frames, settings, the large amount of validations, and so on.

nitelyon There isn't much point to HTTP/2 past the load balancer

> I think ReadableStream/WritableStream APIs on browsers were supposed to change that, but I haven't followed the progress in the last few years.

There has been a lot of pushback against supporting full-duplex streams[0].

[0]: https://github.com/whatwg/fetch/issues/1254

nitelyon There isn't much point to HTTP/2 past the load balancer

> A h2 proxy usually wouldn't proxy through the http2 connection, it would instead accept h2, load-balance each request to a backend over a h2 (or h1) connection.

Each connection need to keep state of all processed requests (the HPACK dynamic headers table), so all request for a given connection need to be proxied through the same connection. Not sure I got what you meant, though.

Apart from that, I think the second sentence of my comment makes clear there is no smuggling as long as the connection before/past proxy is http2, and it's not downgraded to http1. That's all that I meant.

nitelyon There isn't much point to HTTP/2 past the load balancer

In theory request smuggling is not possible with end-to-end HTTP/2. It's only possible if there is a downgrade to HTTP/1 at some point.

nitelyon Writing secure Go code

They are going to add boilerplate free error handling sooner or later. There are many proposals for "Go 2" already.

nitelyon Mitmproxy 11: Full HTTP/3 Support

Something not mentioned: web-browsers limit the number of connections per domain to 6. With +http/2 they will use a single connection for multiple concurrent requests.

nitelyon Recent Performance Improvements in Function Calls in CPython

If those libraries are doing something at import time, then it could take any amount of time, TBF.

nitelyon A bunch of programming advice I'd give to myself 15 years ago

I'll second this. There are a lot of good managers that care more about the product than some team metrics. Same for coworkers that care about improving. Don't let one bad manager define how you'll do things in your next job.

nitelyon Regular expression matching can be simple and fast (2007)

Look-arounds can be implemented in quadratic time for unbounded expressions (i.e: containing +, *), and linear time for bounded expressions quite easily. And I suspect they can be implemented in (super)linear time in general by matching them in parallel to the NFA.

nitelyon Becoming a dungeon master for an interview

Explaining the reasoning while solving the code puzzle is the most important part, though. Just being able to solve them without speaking a word has never been enough. Unless you are talking about automated coding tests (but that also has never been enough).

nitelyon Why do programmers need private offices with doors?

idk who wins, but I'd assume extroverts need a quiet environment to be able to focus as much as anyone else.

nitelyon The Shunting-Yard Algorithm (2011)

I implemented a variation long ago to parse regular expressions (regex) [0]. Albeit I did some pre parsing for things like character classes and lookarounds.

[0]: https://github.com/nitely/nim-regex/blob/5e447c329ce826deb61...

edit: added permalink

nitelyon Getting a job at Apple without going to college or doing LeetCode

How can you test all of that? through leetcode kinda questions you surely cannot. Maybe behavioral questions are close, but you would do those in both types of hiring processes, no?

nitelyon People lining up in Argentina to have their iris scanned for Worldcoin

It's close to presidential election in Argentina. Gov won't do anything that gives them bad press. Plus I don't think they care at this point.

nitelyon Why can't you reverse a string with a flag emoji?

CPython 3 does use UTF-32 under the hood for strings (there is bytes for plain sequence of bytes). As you say, it's the worst of both worlds. High memory usage, and not really useful if you are dealing with unicode characters (grapheme clusters).

My impression is most modern languages that bother with unicode (swift, rust, nim) are using utf-8, and doing linear time operations to handle unicode. I think that's the right approach, as I don't recall ever needing random access on a unicode string.

nitelyon Why can't you reverse a string with a flag emoji?

Of course it's possible, the Unicode standard even has a table[0] you can use to build a DFA (Deterministic Finite Automata) to break up a string into grapheme clusters. You can reverse the DFA to match and yield the graphemes backwards as well, which will give you the reversed unicode string.

[0]: http://www.unicode.org/reports/tr29/#Table_Combining_Char_Se...

nitelyon Why can't you reverse a string with a flag emoji?

You can, but you need to break the string into graphemes first.

nitelyon OO in Python is mostly pointless

If we go by Alan Kay's definition, then we can argue Elixir/Erlang is an OO language [0]. It's not the first language one would think of when talking about OOP, is it?

To me, OOP is all about implementation details.

[0] https://elixirforum.com/t/the-oop-concept-according-to-erlan...

nitelyon Regex literals optimization (or how to cheat on benchmarks)

That's good to know. Is there an implementation of it? I know of TRE, regex-tdfa, ocaml-regex-tfa, and re2c, they all implement Laurikari's algorithm (or a variation of it), but have POSIX semantics.

nitelyon Regex literals optimization (or how to cheat on benchmarks)

AFAIK, RE2 does not implement a tagged DFA. It implements a DFA that runs when captures are not required and/or to find a match within the text and then it runs the NFA to record the captures.

I'm aware of Laurikari's algorithm, I'm not aware of it being correct[0]. Also, their algorithm has POSIX semantics, RE2 (and most PLs regex engines) has PCRE semantics.

[0] http://lambda-the-ultimate.org/node/2064#comment-25469

nitelyon Regex literals optimization (or how to cheat on benchmarks)

It doesn't. RE2 searches for a prefix of literals. If the regex doesn't start with one or more literals, then the full regex engine is ran.

nitelyon Regex literals optimization (or how to cheat on benchmarks)

Yeah, nim-regex is based on NFA. I'm not aware of a pure DFA that is correct and also supports those. I built an hybrid a while ago[0], but it's slower than nim-regex when it needs to capture/assert, I should profile it and find out why some day.

[0] https://github.com/nitely/nregex

nitelyon Python Pip 20.3 Released with new resolver

They either haven't experience the pain or are oblivious to it. Pip old resolver is borked[0]:

> [The new resolver] will reduce inconsistency: it will no longer install a combination of packages that is mutually inconsistent. At the moment, it is possible for pip to install a package which does not satisfy the declared requirements of another installed package. For example, right now, pip install "six<1.12" "virtualenv==20.0.2" does the wrong thing, “successfully” installing six==1.11, even though virtualenv==20.0.2 requires six>=1.12.0,<2 (defined here). The new resolver would, instead, outright reject installing anything if it got that input.

[0]: https://pyfound.blogspot.com/2020/03/new-pip-resolver-to-rol...