Kudos on your bold undertaking! I've been a side-lined QNX admirer for some time, though not a potential user in most cases. A good next step would be a series of blog posts where the author takes on common types of enthusiast projects and unpacks how QNX's strengths can be applied in those scenarios.
Do you find you really need that level of “resolution” with memories?
On our [1] chatbots we use one long memories text field per chatbot <-> user relationship.
Each bot response cycle suggests a new memory to add as part of its prompt (along with the message etc)
Then we take that new memory and the existing memories text and feed it to a separate “memory archivist” LLM prompt cycle that’s tasked with adding this new memory and resummarizing the whole thing, yielding a replacement for the stored memories, with this new memory added.
Maybe overly simplistic but easy to manage and pretty inexpensive. The archiving part is async and fast. The LLM seems pretty good sussing out what’s important and what isn’t.
I have already tried what you're doing, and it didn't perform well enough for me. I've been developing this project for a two years now. Its memory isn't going to fit in a single prompt.
I imagine that your AI chatbots aren't as cheap or performant as they can be with your potentially enormous prompts. Technical details aside, just like when talking to real people, it feels nice when they recall minor details you mentioned a long time ago.
If it's your personal assassinate and is helping you for months it means pretty fast it will start forget the details and only have a vogue view of you and your preferences. So instead of being you personal assassinate it practically cluster your personality and give you general help with no reliance on real historical data.
I have read a lot of reports that the job market is pretty bad.
But, bad or good, I think all you can really do is keep trying! Don't let a few rejections stymie your long term goals. Your family needs you to keep putting one foot in front of the other and applying to more and more places until you find that perfect role.
Maybe use this downtime to build yourself up: open source some stuff that defines you as a subject matter expert, or blog about some of your experiences, etc.
Wouldn't hurt to share your resume here too - lotta industry people lurking. :)
Sad day! This guy was a hilarious and talented writer. If anyone is looking for a book to pick up this weekend, I'd recommend checking out some of his work, especially if you like hard drinking Jewish nihilist detectives.
I loved Kinky. I first encountered him in a Washington Post interview in the early 1980s, in which he remarked "I'm searching for a lifestyle which does not require my presence." That's been my lodestar ever since. R.I.P. Kinkster.
Fortunately, that is indeed a thing :) several post-processing tools have some sort of gfpgan_strength (searching as-is should yield results on a few repos) param being passed, also it's been a while since diffusion-based restoration methods are equipped to diminish stochasticity enough to produce great results, worth the time as well!
Also noteworthy: https://openmodeldb.info/?t=faces+restoration+texture-genera...
Hah, so high tech- Turns out the said repos used to do the same, then one of them later added CodeFormer under the hood, conflated the strength with affinity and didn't bother renaming (calling codeformer --gfpgan_strength looks very unhinged to me but oh well haha).
It's definitely doable though! What I had in mind as a GAN equivalent (used to apply in WSI context while back) is akin to Rayleigh EigenDirections in terms of latent space navigation https://www.ecva.net/papers/eccv_2022/papers_ECCV/html/7277_...
There's some code out there, unsure if it's streamlined for this use case but can lend a hand if you decide to give it a shot :)
Always surprising to click through a link on HN and discover it is one's own work. For a time I was very interested in lightweight array-based implementations of common data structures and this one seemed particularly handy.
It sounds a little like it didn’t work out as well as you hoped. How did it fare?
I am interested because I have some scientific software (astrodynamics - propagating orbits in space) that would really benefit from a cache-friendly tree, and this seemed promising.
It does? Feels like an O(n) scan every time you need to query the children of a node is a nonstarter for most applications (the readme is strangely optimistic about this point). Plenty of cache friendly tree implementations out there, and this one seems actually cache hostile with few benefits in my mind aside from ease of implementation.
Also, I write a lot of code that runs on a gpu, and the claim that this tree is somehow gpu friendly I find particularly dubious.
> Feels like an O(n) scan every time you need to query the children of a node is a nonstarter for most applications (the readme is strangely optimistic about this point).
The trick is that querying the children of N different nodes is usually still a single O(N) scan, so if you operate on it array-style (which APL heavily encourages anyway), it's amortized constant time. Of course that's not always viable, but APL programmers tend to be surprisingly good at making array operations out of things you wouldn't expect to use arrays for.
> cache hostile
If you additionally enforce that all parent indexes point to lower numbers, a preorder traversal is a linear scan forward, and a postorder traversal with child order reversed (which you can usually correct for one way or another) is a linear scan backward.
(This assumes you only need dependency ordering, ie the parent node uses or supplies data to/from its children; if you need a true sequential traversal, the array has to be sorted according to that traversal (but is still a valid Apter Tree).)
> the claim that this tree is somehow gpu friendly I find particularly dubious
Yeah, array programming is generally kind of hit-or-miss at that and this does look like a miss.
Whenever somebody says cache friendly without additional context I assume they got code from somebody else without understanding what makes things "cache-friendly".
For a arbitrary Apter Tree, a linear scan is unordered. You can impose additional constraints to get a ordered traversal (in the same way that, eg, you can sort a assoc-list/JSON-style key-value table by keys to get a key-order traversal), and the result is still a valid Apter Tree (respectively valid list of key-value pairs).
Yes but that is not what is presented (a B+ tree is not a B tree even with minor modifications) and it changes the complexity of your other update operations drastically. The thing that grates me (as someone that has written a dozen or so different tree structures) is that this one is presented as a particularly good one, and I think it excels at almost nothing, hence its obscurity.
For me, N is small. Its also N-ary, not binary, which crosses off a bunch of the first options. Anyway, I am not sure this will work, just worth trying. Empirical numbers beat theory every time :)
You are using N in a different sense than I am. Unless I'm reading the tree description incorrectly, N is the size of the tree itself, not the number of children.
I would hazard a guess that a regular n-ary tree would outperform the OP tree in many usage scenarios with no extra effort, and with a number of B+ tree variants being strictly better at the cost of more effort.
The point is that you shouldn't try to get all the children of a single node, but rather all the children of all the nodes, which is still O(n) and not O(n^2).
I deal with very large tree structures (~100 GB) in my search engine, but even there the dominant factor for performance isn't big O, but reducing block reads, access patterns and keeping relevant data in the disk cache.
Big O isn't irrelevant, but it is not the full story either. There's a solid reason why hash tables are a thing in memory but aren't really a thing on disk.
Do you understand the data structure being proposed in the original post, and are you claiming that scanning 100GB of data every time you want to perform a childof operation is acceptable? Please, use the proposed tree for your application since big o isn't the full story to you lol
I'm not sure why you're suggesting those claims were made. The parent appears to be talking about non-asymptotic behavior. Very often algorithms with worse big O perform better; its use-case specific. Hyper focus on big O isnt productive, but fairly common due to how CS curriculums focus on it. In some cases it takes unexpectedly long for the big-O to impact performance, as other factors dominate.
The parent commenter writes a wonderful blog that covers their experience with building and optimizing a search engine, well worth a read.
Then perhaps I'm misunderstanding you. When N is *sufficiently* large, I think we all agree that you'll prefer an algorithm with better big-O.
When N is small, the asymptotic behavior is irrelevant and that's easy to show. Let's say we're comparing a O(N) algorithm to a O(N^2) algorithm, but each operation of the O(N) is 1000x more expensive. The O(N^2) algorithm is preferred as long as N < 1000. Choosing the O(N) algorithm will hurt performance in those situations. Real world examples like single-byte-writes causing full pages to be re-written on SSDs shows this isn't just a mathematical curiosity.
Without benchmarks, analysis of big-O behaviors, usage patterns, and known data size I'd (personally) avoid guessing the performance of Atree in an application.
Are you saying something different? It sounds like you have much more SIMD experience than I do and I'm always happy to learn something new.
Big O tells you that there exists some number N such that for each number m larger than N, if O(f(m)) > O(g(m)) then f(m) > g(m). In practice, N may be 10, or it may be larger than the number of atoms in the universe. It's unrelated to the number of items in your collection, but a property of the algorithm itself.
I'm not sure why what I wrote necessitated a lesson on limits and asymptotes. My point was that given that N was the size of your tree, more often than not, big-O analysis would apply in this case since N is likely big compared to secondary fixed effects.
I still like that setup for using trees in low level languages.
But personally I’ve been working at higher levels of the stack the last few years, where these kinds of decisions seem less important.
And on another level, it seems like coders in general aren’t that interested in vector oriented languages and techniques which makes their study somewhat isolating.
"Isolating" is where the performance (innovation) is.
I used a very similar setup, first time I needed to implement a tree. Now, I'm a fan of Eytzinger layout. (referenced in a previous comment in this thread)
Yeah, most coders in general don't seem to be as interested in this stuff, but it's still necessary. They'll want more performance.
Why do they need more performance? Hardware gets faster all the time, and the most popular implementations of the most popular programming languages have so much low-hanging fruit you can get a 10x improvement by rolling your cat on the keyboard.
I don't think programmers actually care about performance as much as they care for convenience. Every year the stack moves a bit higher, and everyone is okay with websites taking days to load on brand new phones with Gigabit wireless connections. There are companies that care about performance on the margin, like stock trading firms, but to get into one of them, you have to get pretty lucky, or come from a pretty special background. Even the banks are using Python more and more, these days.
People will always care about performance because they will always want more functionality.
I bet you care about the performance of your database or how fast your pages load. You want your streaming videos to be skip-free and your phone calls to sound lifelike. Performance will always matter. Because while people like me will be always trying to squeeze more, "the other side" will always be ready to use it for some new feature.
The post you're replying to sounds more like it's lamenting the complacency of most developers more than it's saying that performance isn't worth caring about, or I'm projecting my own feelings onto it.
I'm not under the impression that people care at all, to be honest, outside of certain communities. If you're not in those communities talking about performance as a corner stone feels mostly like screaming into the void.
It does help (roughly ~5x vs. pointer-chasing trees, probably can be further optimized) for my workload, but at the same time quite some time was spent just making sure the tree is correct.
I'm interested in the same stuff/area. There's a lot of great results to read, check out cache-oblivious B-trees by Dr. Demaine (or honestly anything by him.) This link is a good distillation of some of the concepts. https://algorithmica.org/en/eytzinger
I'm _also_ interested in scientific software, but that's more a hobby than a job. =)
For propagating a large number of orbits in space, I'm really curious what the Correct (tm) numerical algorithm is, mind sharing more? I love that space right at the intersection of lots of math + need to understand how computers really work. Once upon a time I implemented fast multipole method for the n-body problem, but I certainly don't claim to deeply understand it, anymore. :)
reply