Hacker News Reader

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

Glad to hear that :D One of my main goals was to show the entire progression of how I approached the problem, instead of just saying "here's the final result".

I have another article that covers profiling in more detail, you might find it useful: https://death.andgravity.com/fast-conway-cubes#intro-to-prof...

Note that besides the cProfile text output, there are better, graphical tools for profiling; I've personally used pyflame+flamegraph.pl, and tuna.

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

You can, see the next paragraph, "also narrow down around the estimated position iteratively..."

I gave up because I was too lazy to think how to do the "precompute the maximum +/- error bounds" jiggawatts mentions in https://news.ycombinator.com/item?id=34021826

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

I did try mmap, both with the plaintext binary search, and with the binary file (you can find a note about it in the HTML source :)

I ended up not mentioning it because for some reason, it was ~twice as slow on my mac... I'm now curious to try it on a decent Linux machine.

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

(replying with more details, because I think it's pretty cool, and I'll definitely try this out)

The linked item is to https://blog.mro.name/2022/08/pwned-diy/, where the author converts the passwords list to a CDB (Constant DataBase) file, a simple, fast lookup database format created by D. J. Bernstein.

https://cr.yp.to/cdb.html

https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

Hey, I didn't know about this command, neat!

On my laptop, look `time`s at ~10 ms (for comparison, the Python "binary search" script `time`s at ~50 ms).

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

Not yet, I might give it a try.

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

You can, Scott Helme wrote some articles about this (I mention them at the end of my article):

* https://scotthelme.co.uk/when-pwned-passwords-bloom/

* https://scotthelme.co.uk/sketchy-pwned-passwords/ – here he uses a count-min sketch to also store the frequency

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

I actually did try this, but I got impatient and stopped it after 30 minutes or so, and a ~20G database file.

For some reason, after that, `ls` in that directory (or even shell completion) would freeze the shell entirely, even after reboot. I eventually managed to delete the file with `rm db.sqlite` (no completion allowed), but even that took like 2 minutes.

I might try again with WAL enabled (based on my shell history, I also deleted a -journal file).

genericlemon24on I almost failed to search a 37 GB text file in under 1 millisecond

(author here) Hey, that's actually a great idea. I remember reading about a fast grep or wc implementation that did parallel reads.

Off the top of my head, I don't really know how to do that (aside from the naive way of using threads), I'm guessing readv[1] might be be useful? Will definitely look into it.

[1]: https://linux.die.net/man/2/readv

genericlemon24on The unreasonable effectiveness of f-strings and re.verbose

I mention PCRE in passing at the end of the article, but I didn't know about (?(DEFINE)...); that's very, very cool!

genericlemon24on The unreasonable effectiveness of f-strings and re.verbose

An infinity! https://xkcd.com/1313/

genericlemon24on Write an SQL query builder in 150 lines of Python

Thank you!

genericlemon24on Write an SQL query builder in 150 lines of Python

For one, it can output more than one flavor of SQL: https://pypika.readthedocs.io/en/latest/3_advanced.html#hand...

Since SQL is ever-so-slightly different across databases, I imagine trying to cover all of them as a single dev is a nightmare (especially if that's not the problem you're trying to solve).

I wrote my own query builder because I know for sure I'm only targeting SQLite. The second I need my feed reader library to work with another database engine I'm dumping my own for something more serious – either a full blown database abstraction layer like SQLAlchemy or Peewee (likely without the ORM part), or something simpler like PyPika or python-sql.[1]

[1]: I talk more about them here: https://death.andgravity.com/own-query-builder#sqlbuilder-py...

genericlemon24on Write an SQL query builder in 150 lines of Python

Yup, after my own initial research I found it as well, and I like it a lot. I talk more about it here: https://death.andgravity.com/own-query-builder#sqlbuilder-py...

genericlemon24on Write an SQL query builder in 150 lines of Python

Hey, thanks for that!

genericlemon24on Write an SQL query builder in 150 lines of Python

> It's magic when it works but it suffers from the drawbacks noted elsewhere in the thread about traditional ORMS...

(Not that there are lots of other devs on my project at the moment, but)

I am managing this by aggressively limiting the size / features of my query builder, so it's (relatively) easy to understand just by looking at the code.

If it ever passes that point, it's probably time to switch to a "real" query builder / ORM.

genericlemon24on Write an SQL query builder in 150 lines of Python

Hey, this has roughly the same philosophy as mine, I might add it to my survey: https://death.andgravity.com/own-query-builder#sqlbuilder-mi...

genericlemon24on Write an SQL query builder in 150 lines of Python

Glad you liked it!

genericlemon24on Write an SQL query builder in 150 lines of Python

That's what the fancier __init__() at the end of the article[1] is for :)

Here's the tl;dr of a real-world example[2]:

    query = Query().SELECT(...).WHERE(...)
    for subtags in tags:
        tag_query = BaseQuery({'(': [], ')': ['']}, {'(': 'OR'})
        tag_add = partial(tag_query.add, '(')
        for subtag in subtags:
            tag_add(subtag)
        query.WHERE(str(tag_query))

It can be shortened by making a special subclass, but I only needed this once or twice so I didn't bother yet:

    for subtags in tags:
        tag_query = QList('OR')
        for subtag in subtags:
            tag_query.append(subtag)
        query.WHERE(str(tag_query))

[1]: https://death.andgravity.com/query-builder-how#more-init

[2]: https://github.com/lemon24/reader/blob/10ccabb9186f531da04db...

genericlemon24on Write an SQL query builder in 150 lines of Python

It's not either-or; I'm using the query builder to build _parametrized_ queries.

Here are two examples:

https://death.andgravity.com/query-builder-why#introspection https://github.com/lemon24/reader/blob/10ccabb9186f531da04db...

genericlemon24on Write an SQL query builder in 150 lines of Python

> What does `query.SELECT("one")` on its own represent?

data['SELECT'].append('one')

I'm intentionally trying to not depart too much from SQL / list-of-strings-for-each-clause model, since I'd have to invent/learn another one.

For a full-blown query builder, I agree Table("table").select("one") is better.

genericlemon24on Write an SQL query builder in 150 lines of Python

I cover this solution here: https://death.andgravity.com/own-query-builder#jinjasql-sqlp...

genericlemon24on Write an SQL query builder in 150 lines of Python

I am using exactly that; the query builder goes on top of it :)

genericlemon24on Write an SQL query builder in 150 lines of Python

Someone on Reddit suggested stored procedures, which seems like a good alternative.

Alas, SQLite doesn't have them, so query building it is.

genericlemon24on Write an SQL query builder in 150 lines of Python

I wrote an entire article about why I didn't do that: https://death.andgravity.com/own-query-builder#sqlalchemy-co...

In general, SQLAlchemy is an excellent choice; in my specific case (single dev with limited time), the overhead would be too much (even with my previous experience with it).

genericlemon24on Write an SQL query builder in 150 lines of Python

Sometimes you need dynamic SQL, because the DB doesn't have stored procedures you can use for the same purpose (e.g. SQLite).

I talk more about this use case here: https://death.andgravity.com/query-builder-why#the-problem

genericlemon24on Write an SQL query builder in 150 lines of Python

> In that sense, if anything this is a downgrade from regular SQL.

It likely is.

Ideally, instead of dynamically building queries, one would use stored procedures.

I'm using this with SQLite, which doesn't have stored procedures, so it's an acceptable downgrade for me. Appending strings to lists gets messy quickly, example: https://death.andgravity.com/query-builder-why#preventing-co...

genericlemon24on Write an SQL query builder in 150 lines of Python

(author here)

Yup, good thing to note, thank you!

I've kinda assumed everyone knows about the named parameters some bindings offer, but that's probably not true. Will add a disclaimer.

In the previous articles, I do talk about how this is an upgrade from plain SQL, not from regular full-blown query builders / ORMs.