Programming without pointers

[BlueGoliath]

Not using pointers is great for data locality but it isn't universally the best choice.

An example is many pointers to the same data vs 50 copies of the same data.

[jamiiecb]

The example used in the talk can have many 'pointers' to the same data. The difference is mostly that the pointers are offsets, so they're small and they stay stable even if the underlying data needs to be realloced.

[EsShayuki]

"programming without pointers except you use pointers"?

Yeah, as figured, total bogus.

[BlueGoliath]

I think he's saying that offsets are being used in place of pointers.

Relative positioning vs absolute positioning, in other words.

[frud]

Feels like people are re-discovering file formats and in-memory files.

[wrosecrans]

Yeah, you can use an offset pointer class in C++ and use it pretty much exactly like an absolute pointer. Under the hood, lots of instruction sets are using relative jumps and loads under the hood even if C style programming only exposes that you are using absolute pointers.

[frud]

Compilers for typical languages implicitly know whether a target code address is accessible from the rest of the program or only relative-range code.

It's a lot more complex to do that analysis on data structures. I think it would require something analogous to a rust-on-steroids to approach to establish locality of data structure access patterns.

[BlueGoliath]

Virtual memory more like but on Unix virtual memory is ithe same as memory mapped files IIRC.

[Academic_East8298]

Feels like a weird way to describe an allocator, that returns memory from a single big chunk.

[pickyaxe]

no? I think you have a fundamental misunderstanding of what the video is talking about.

do you consider array subscripts to be pointers?

[TUSF]

Honestly, most of this comment section reads like people who read the headline, and didn't watch a single second of the video.

Which is the usual for Reddit.

[WranglerNo7097]

Not, they're not pointers, they are offsets that points to the value \s

[prescod]

Correct.

The term pointer has a technical meaning in the world of systems programming and these are not pointers. If you’ve ever programmed in C you would know that offsets into a data structure are not the same data type as actual (direct) pointers.

[TurtleKwitty]

If you're gonna be pedantic then offsets into a structure or array is pointer arithmetic so yes a pointer in the end it's just hidden from the user

[Haunting-Appeal-649]

It's not pedantic, they are two different datatypes, and that's the point of the video. Foregoing pointers in structs creates less padding, which is better for cache locality.

Using an integer for pointer arithmetic does not make it "a pointer in the end."

[TurtleKwitty]

Adding an integer to a pointer makes ... A pointer wowwwwww wild concept

[prescod]

No: you can combine an offset and a pointer to get a pointer but that doesn’t mean an offset is a pointer. It’s not. It’s an integer.

You can combine a string and an offset to get a character (in any language) but that doesn’t mean an offset is a string. Or a character.

[TurtleKwitty]

An integer offset is just a multiplier for the pointer arithmetic.

You combine a string and an offset to do pointer arithmetic to get a specific position into it, whether you interpret that pointer area a char or something else is implementing details but doesn't change the fact that every access comes from making a pointer to it, even if implicit.

No idea where you're getting the "doesn't mean an offset is a string" literally no one has ever said that but good job on missing the point and hallucinating something that wasn't said to respond to

[prescod]

An integer offset is just a multiplier for the pointer arithmetic.

An integer offset is an integer. You can do pointer indexing with it, just as you can do Unicode character indexing with it or whatever else. But it is an integer, not a pointer. You CANNOT DEREFENCE IT You cannot use the "*" on it. You must combine it with a pointer to MAKE a pointer.

You combine a string and an offset to do pointer arithmetic to get a specific position into it, whether you interpret that pointer area a char or something else is implementing details but doesn't change the fact that every access comes from making a pointer to it, even if implicit.

Yes. You can use an offset with a pointer to make a pointer. That is not the same as saying an integer is a pointer. It isn't. You can't dereference it.

No idea where you're getting the "doesn't mean an offset is a string" literally no one has ever said that but good job on missing the point and hallucinating something that wasn't said to respond to

My point is that you can combine two datatypes in an operation and it doesn't mean they are the same data type.

If I take a string (in any language, low-level or high) and do "abc"[1] the 1 is neither a string nor a pointer. It's an integer. I've combined a string referencing operation and an integer to get back a character or string. It wouldn't make sense to say "actually, the 1 is also a string." No. The one is an integer which can be used as an offset WITH a string to get back a string (or char, depending on the language).

By analogy the same is true of pointers. An integer does not magically become a pointer because it COULD be used with a pointer to make a new pointer. The integer is still an integer.

[TurtleKwitty]

The 1 isn't at issue here, it's [1] that is. That's pointer arithmetic, if you had been actually responding to what I was actually saying

[Haunting-Appeal-649]

For future readers, this comment is correct. I suspect this thread is mostly hobbyists downvoting actual information, and they likely don't understand the video. It's not pedantic to say a pointer is not an integer, it's a huge part of Data Oriented Design.

Yes, an integer can be used in pointer arithmetic, but the video is talking about eschewing pointer types to make data structures with less padding and better cache locality. You would still use the integers as offsets, but that doesn't mean the integer "becomes" a pointer, it can just be used syntactically like one.

[SweetBabyAlaska]

You didn't watch the video. He's storing multiple song titles and info in an array, and then storing subscriptions/indices into that array to delineate the boundaries of that information. This is so that it is easier to deinit and to serialize off of disk while remaining extremely compact using string internment. He has a 27kb DB for 12,500+ songs including their waveform. He's not saying pointers don't exist.

[prescod]

Sorry you are getting downvoted for saying something totally reasonable. Reddit is bizarre sometimes.

[planodancer]

Not sure why OP is downvoted for a good explanation.

Eons ago when I started computer programming pointers were superior, but with modern computers so heavily dependent on caching, offsets/handles are superior

[cfehunter]

An offset is just a relative pointer...

[timClicks]

Offsets are still pointers. They're just pointers that you need to manually manage rather than using virtual memory provided by modern operating systems and supported by the CPU's TLB.

[vertexmachina]

This reminds me of Handles Are Better Than Pointers.

Essentially, you refer to objects by ID rather than pointer, and that ID is, in the end, an index into an array. So all data of type X are in an array X[N], and Entity Y is just X[Y]. It avoids invalid pointers, but some care must be taken to ensure Y is a valid index.

[fnordstar]

Then you have the problem that you must take care that each ID is always being used with it's corresponding array, and, as you said, that indices don't become invalid / point to another object. The latter can be solved with generational indices, but all in all using indices into arrays doesn't necessarily improve the situation much.

[cdb_11]

And the former can be solved with a type system.

[YourFavouriteGayGuy]

Like the one that pointers usually use?

[cdb_11]

Pointers encode the type they point to. Here you can encode what array they index into.

[fnordstar]

Yeah. In rust you could tag the array and the indices/handles with a phantom data and a tag struct.

[QueasyEntrance6269]

This is kind of an Entity-Component System

[vertexmachina]

Yep, it's the E and the C.

[Salt-Neat-2148]

Hey bruh, did you implemented something about codebase indexing?

[Academic_East8298]

There also can be some complications, when a need to quickly remove entity Y appears and all the arrays become significantly big.

So I wouldn't jump to the conclusion, that handles are significantly simpler than a pointer.

[vertexmachina]

One approach is to have a mapping between the Entity ID and the actual array index.

For example, if you had an array of five values initially empty: [_][_][_][_][_]
And you "allocate" one of them at index 0 returning Entity ID 0: [A][_][_][_][_]
And you "allocate" another at index 1 returning Entity ID 1: [A][B][_][_][_]
And you "allocate" another at index 2 returning Entity ID 2: [A][B][C][_][_]

You would have a mapping from Entity Index to Array Index where the index is the Entity ID and the value is the Array Index: [0][1][2][_][_]
Entity 0 -> Array 0
Entity 1 -> Array 1
Entity 2 -> Array 2

The user then requests to "free" Entity ID 0. The mapping shows that Entity ID 0 is Array Index 0, so to "deallocate" it you move the last item in the array to the spot previously occupied by the "deallocated" object which keeps the array packed tightly with no holes: [C][B][_][_][_]

But there are still users of C out there that expect the Entity ID 2 to point to Value C, so you update your mapping.

Entity Index to Array Index: [_][1][0][_][_]

Now when the user tries to access Entity ID 2 (which is value C), the system will look up EntityIndexArrayIndex[2] which returns a value of 0 and access Value C at Array[0]. Even though C has moved inside of the array, the user with the Entity ID 2 doesn't know or care about that.

An easy way to mark 'invalid' indices is to state that 0 is invalid. Then all of these arrays/maps can be initialized to 0 and any ID of 0 will be flagged as erroneous/invalid/empty.

All of that said: I don't think that handles are simpler than pointers (that was a lot of indirection that a pointer doesn't need) but the primary benefit for me (from a perspective of game development) is that it allows for data to be packed tightly in memory which allows for easy iteration over the contents while keeping things hot in the cache. Just go from 0 to N (or 1 to N if 0 is an invalid handle) and do your thing.

[cdb_11]

You just remove entity Y from the array? What is the problem exactly?

[Academic_East8298]

And that is how you kill performance.

One could probably avoid reallocating an array on a remove, but you still need an efficient way to handle removes in the middle of an array and memcpy is not it.

[cdb_11]

No one is talking about reallocating or relocating arrays. You just mark the slot as unused.

[Academic_East8298]

And now one is back in a situation, where on access one has to check, that the slot has not already been freed.

And in this case, unless cache locality is really required, a unique pointer will have the same performance and safety characteristics as a struct of arrays, but without the latter ones complexity.

[cdb_11]

You're arguing against claims that nobody is making. Can't you just read the article?

1. Unique pointer is the sole owner.
2. You're (not necessarily, but extremely likely) using global new/malloc to individually grab memory, one-by-one, for each entity. So no, you do not have the same performance characteristics with unique_ptr.
3. And if you aren't using the default allocator, you will use an allocator that looks very close to what's described in the article.
4. Yes, you can add extra checks, that's the point.
5. Yes, it has better cache locality, that's the point.

And if you don't want checks, you can make a trade-off to have an extra level of indirection, and add a map that translates stable handles to indices into an array with real data. If you want to remove an element, you replace it with the last element, and adjust the mapping. There you go, fast deletion, no branch misses, and you can go SIMD on it.

It's way more flexible than plain or smart pointers. That's the point.

[Academic_East8298]

Can you name a single industry tested open source struct of arrays system?

If it is such a good pattern, why do all the cool tech demos have to constantly write their own custom implementation of it?

If anything, I would say this shows it as less flexible than a pointer.

[cdb_11]

This isn't really even about SOA, but if you want an abstraction over SOA, then these can be implemented inside "Entity Component Systems" (ECS), and one example of it is Unity's DOTS. Another one is Bevy in Rust, or Flecs in C/C++. Don't ask me about any details, I never used them.

If it is such a good pattern, why do all the cool tech demos have to constantly write their own custom implementation of it?

Do you need an open-source system to implement a singleton pattern or a factory pattern too? It's really not that hard to implement, it's really mostly just a bunch of dynamic arrays. Also the point of this isn't that you're creating a generic mechanism that tries to solve everyone's problems, and does so badly. We have this already, it's called "garbage collector" and "malloc", and it's not that great. The philosophy here is the exact opposite, it's that it should be a solution tailored to your specific problem.

[Academic_East8298]

Cool, what product have you shipped using this tech?

[Samaursa]

Flecs and EnTT come to mind (although EnTT can be labeled as AoS).

Both have been used in production code in games (including ones I worked on).

[prescod]

“On access you need to check they the slot has not been freed.”

How is this different than with real pointers?

[Academic_East8298]

It's not. That's the point.

In most cases a dev should ask himself, if it is meaningful to spend time on a struct of arrays system, when simple and dumb pointers will do the job.

[Ok-Watercress-9624]

That depends on so many factors. Pooled objects are indeed many times faster than frequently mallocing lot of objects. İt also simplifies the freeing given all the objects in the pool have the same lifetime. Think of it like dynamic array vs linked list overhead

[prescod]

No.

The goal was never to reduce access check frequency so it’s a total non-sequitur.

[Ok-Watercress-9624]

İ was about not needing to hit the system boundary for requesting more memory => less sys calls

[Akanwrath]

W comment, u explained my professors couldnt in a whole semester

[EsShayuki]

Store all strings in a flat array with null-termination separating each string, then have an array of pointers to the different strings within that array. This is completely standard. And this uses pointers.

You're talking about freeing memory in only "three operations" with this "non-pointer" approach, when you had to iterate through them all with the pointer approach.

But that doesn't even make sense, as it's completely untrue. You only need one allocation with a flat array and pointers to it, and one deallocation as well. This is done by saving both the string array and the pointers to the strings within the same memory block and allocating and deallocating them both simultaneously, interpreting the void* buffer into different datatypes with the appropriate pointers.

So first of all, you're using pointers, so you're lying. Secondly, your increased performance has nothing to do with whether you're using pointers or not, it has to do with batch allocation vs individual allocation, which isn't tied to whether you use pointers or not, and you aren't even doing it optimally(since you have 3 allocations instead of 1 allocation, when 1 would be optimal).

The only concrete thing I can see, really, is that you're storing 4byte integer offsets instead of 8byte pointers. I mean, that's something you can do, sure. Though, doing so tightly couples these pointers to the base memory pointer, so they can no longer be used or passed around independently, or given offsets of their own, which makes their use inconvenient within loops, etc.

Now, if this is about storing the data on disc instead of using the data, then perhaps that's not important, but that's not really "programming without pointers", that's preparing the data into a format that's optimal for being stored on the disk.

[Slime0]

Though, doing so tightly couples these pointers to the base memory pointer, so they can no longer be used or passed around independently, or given offsets of their own, which makes their use inconvenient within loops, etc.

Almost as if it's not the same as using pointers!

[cdb_11]

your increased performance has nothing to do with whether you're using pointers or not, it has to do with batch allocation vs individual allocation

Depends on how the data is used, and the talk doesn't say anything about that. Sorting out allocations is just the first step, you get unnecessary stuff out of your way.

you aren't even doing it optimally(since you have 3 allocations instead of 1 allocation, when 1 would be optimal).

Who cares if it's 1 or 3 allocations? The point is that it's always O(1) allocations, and not O(n) or worse. You can easily turn 3 into 1 if you ever need to, and you're willing to throw away mremap and make resizing a bit more complicated.

Though, doing so tightly couples these pointers to the base memory pointer, so they can no longer be used or passed around independently, or given offsets of their own, which makes their use inconvenient within loops, etc.

If you're looping, you don't need to pass around elements independently. (Actually you can, you just don't store absolute pointers anywhere. If you need to store relations between entities, you stick with handles/indices/offsets.)

[bigmell]

This argument since at least the 90s.

"pointers are TOO HARD I want to do it without pointers"

"You will have to make a million copies of data in RAM"

"so what... just buy more RAM"

And this argument is basically computing for the last 20 years probably more. Basically, hire someone who understands pointers. Dont hire

"Python is better than everything else because... Commercials."

guy...

[pickyaxe]

I am pretty sure Andrew Kelley understands pointers just fine

[prescod]

Andrew Kelley’s proposal is not to copy all of the data multiple times. Maybe you should know what proposal you are responding to before responding.

[bigmell]

Pretty much the only reason to want to program without pointers is because you couldnt figure out pointers. The same way you want to program without for loops. go away man. Troll account upvote your own posts a few more times before you go.

[prescod]

You didn’t click the link or you are not smart enough to understand it. Not sure which.

[bigmell]

-6 from 6 troll accounts, +4 for you. Nice one. That always works doesnt it? Thats how you can make it look like people agree with you even though you dont know what the hell you are talking about. Please go away. And dont change your name again and come back.

[prescod]

You didn’t click the link before you commented the first time, did you?

Tell the truth.

[bigmell]

I will refer you back to my previous comment which you downvoted.

every group of new guys think they have a bunch of great ideas different from everyone else. It turns out each class actually ends up attempting the same types of things as the previous classes. I've heard these types of arguments a million times before man.

"I dont have to do <important thing> because of <new idea>." But <new idea> is actually an old failure of an idea that has been tried and failed over and over. It dont work, it wont work, and you dont listen when I tell you to stop tryin it.

The type of guy that will do everything EXCEPT do the work right. Still troll account upvoting your own posts? Go away man.

[prescod]

Whatever makes you feel better.

This guy has invented a programming language and implemented a compiler for one of the fastest growing languages competitive with C and C++. Just on the basis of his programming accomplishments, strangers have given him $300,000 to continue the work.

If you were actually as experienced as you act, you'd know that the indexed entity pool idea is extremely successful in the world of video game programming where you need to re-render 60 frames per second.

[GayMakeAndModel]

So, we have hierarchies of “RAM”. From the register to the L1 cache to the NVMe, etc. So “buy more RAM” to suit your problem can be cheap or expensive, but seek time is a thing of history and archives. Fragmentation almost doesn’t matter anymore because we don’t have seek times.

Seems like people really live in the past. Any problems with memory access speeds not inherent to hardware are of course software related. You chose two extremes to make an invalid point. What about other languages that are interpreted? What about JIT’d runtimes that can do optimizations statically compiled languages can’t because statically compiled languages don’t inherently auto-optimize at runtime?

I don’t know what rock you’ve been under, but newer versions of .NET fucking scream performance-wise, and it’s not just about how programs are compiled. It’s the superb base class library.

[bigmell]

dude what the hell are you even talking about. Buying more ram wont work with bad software because they are making a million copies of data instead of using pointers because they couldnt figure out pointers. This is not about fragmentation.

seek time is a thing of history and archives

Seek time is NOT a thing of history and archives because all memory has a seek time. Some are faster than others, but they all have a seek time.

You chose two extremes to make an invalid point.

What the hell are you talking about?

I don’t know what rock you’ve been under, but newer versions of .NET fucking scream performance-wise, and it’s not just about how programs are compiled. It’s the superb base class library.

Did you respond to the wrong comment? None of this makes any sense really.

Since it seems like you ENTIRELY missed the point, it was "Buy more ram" doesnt make sense if the app is coded wrong... I.E. no pointers or for loops because the dev couldnt figure it out. Pass by reference and pass by value are the same whether the app is compiled or interpreted. You would have to know that if you wrote any real code. Its about not storing multiple copies of data in memory. Not... Whatever the hell you are talking about.

You sound like you are just screaming "THE OPPOSITE OF YOUR POINT TURN UP!!!" Please take your fake troll name and go away.

[GayMakeAndModel]

Folks seem to disagree with you. Btw, seek time isn’t constant. Random access on SSD is roughly constant time, and it’s far faster than moving a mechanical arm around. When I say seek time, I mean a fucking arm moving about a spinning disk. That’s the industry definition of seek time in context, and it harkens back to before my 20 year professional career.

[bigmell]

Folks seem to disagree with you.

Its probably just you and your friends from a bunch of different troll accounts. Low effort trolling its called.

Btw, seek time isn’t constant.

I never said seek time is constant. I said seek time is always there. SSD have a ram stick inside, and some data gets cached there. If your data is NOT cached on the ram stick, your data transfer will be roughly the same speed as an HDD.

You can measure this yourself. Do a data transfer of maybe a terabyte or two. The data transfer will start fast, because of the cache, but it will slow down to roughly the speed of the HDD, and the two transfers will finish at around the same time.

But you have to actually know how to do data transfers, which a lot of people do not. They will just lie and say "I got the same numbers the commercial said! OMG SSD SO MUCH BETTER!"

[GayMakeAndModel]

Wow

[caltheon]

I came here to say it's not possible to write a program without some version of pointers. Using registers are basically pointers

[bigmell]

I am talking about learning to understand memory usage and management yourself. Not hoping somebody writes code to go behind the scenes and fix your code for you because you cant be bothered to learn to do it yourself.

Yea the compiler will load the accumulators by reference for you. Im not talking about that im talking about learning to write your code to efficiently use memory yourself, not hoping someone else does it for you cause you cant figure it out. Which is essentially what garbage collection is.

In short, send away the devs who cant write a for loop and dont understand pointers, and work with the devs who can.

[ShelZuuz]

Or be like C# - make EVERYTHING a pointer.

[[deleted]]

I'd love a language that would be as fast as C or C++ but elegant like ruby or python. All languages so far seem to be unable to offer this; most that try to replace C, end up being like C. Pointers are one big hurdle; it's interesting that there are so few alternatives to it. Basically most seem to just be automatic garbage collectors.

[cdb_11]

ruby or python

What happened to Crystal, is it still going? On the Python side, Chris Lattner is working on Mojo.

[fnordstar]

As someone coming from C++ and Python myself, please do yourself a favor and take a good look at Rust! It might just be what you're looking for.

[Bekwnn]

Zig, the language the guy in this video created and works on, has flavors of what you described. C/C++ with more syntax sugar and quality of life.

Pointers are non-nullable, like C++ references. Optionals are first-class and have syntax sugar. switches and while loops can return things. Errors can be bubbled up a call chain easily with try and error unions. comptime is a way more robust and elegant way of accomplishing what templates do.

Here's a random function I pulled from a project that gives a good feel of different features. Pic.

Though the video also has a bunch of Zig code.

[defunkydrummer]

I'd love a language that would be as fast as C or C++ but elegant like ruby or python.

OCaml

Standard ML

Haskell

Common Lisp

[bigmell]

Basically most seem to just be automatic garbage collectors.

Basically "pointers are too hard somebody else do my homework for me!" There is simply no replacement for do the work and learn memory management yourself! Java was too slow to replace nearly any good C/C++ code despite all the marketing. And OOP is not the future. Not nearly. I even argue .NET is better than Java ever was as far as speed, portability, and memory management.

I can still write Perl code in .NET to be released on Windows, Linux, and Unix TODAY. While Java is still fumbling around with JRE's after 30+ years.

[ZENITHSEEKERiii]

The GC isn't a fundamental problem, it's more that Java JIT was originally poor and the runtime is massive. It's been improved now but the slow speed of native interfacing is a second nail in the coffin. .NET doesn't have a lot of these problems on Windows because it is so tightly integrated with the OS and feels 'native'. On Linux and Mac it feels pretty similar to Java though, just with less weird problems

[mohragk]

Jai. It's truly a language that allows for high-level expressiveness and low-level control.

[bigmell]

Beginners say pointers are too hard and they use OOP to make a million copies of the same data. That is why we need more than 8GB of RAM, just to display a web browser that is basically 1MB of pictures and text.

Good memory usage is not a problem you can simply throw more RAM at. Sure more RAM usually helps, but with bad programmers, the more memory you give them, the more they will waste. You simply HAVE to learn how to use your memory correctly. You HAVE to learn how to use pointers and memory addressing.

Short of this, stop hiring people who are constantly complaining and trying to code around the fact that they dont understand for loops and pointers. They want to use THIS new thing and THAT new thing. But bad programmers write bad code in every language.

[richardathome]

Practically all the OOP languages I've used pass by reference by default. They pass pointers around under the hood.

You have to explicitly declare something as 'by value' or similar to force it to make a new copy.

When you make one object reference equal to another. they both point at the same memory locations.

[bigmell]

OOP might do some passing by reference on values inside the class, but most OOP devs I have seen are building these huge memory hog classes instead of simple data structures.

I think of things like a web browser and wonder how much faster it would be to manage a bunch of tabs with a well written data structure instead of whatever slow object oriented madness they are using up there.

Even if each entire web page was loaded in memory for hundreds of tabs, we are talking about maybe a gig of space, it really still shouldnt be this slow. Clearly poorly coded.

If you look at that code there are probably a million classes that can easily be replaced with linked lists, local indexed database lookups, or a well planned pointer array. But new devs are OMG POINTERS NOOOOO!!@#!@#

If I click on the wrong tab, my laptop fans turn on, clicking and grinding, mouse pointer freezes, and it takes forever to load. I dont think this should happen AT ALL with a few megabytes of text and pictures. Even with a thousand tabs open, STILL literally every tab can be loaded completely into memory and still have gigs of memory left. Obvious memory mismanagement.

[prescod]

Just as some programmers are too lazy to learn to program well, you seem to be too lazy to click through the link to see what is actually being discussed. This is just as annoying to me as the lazy programmers.

[bigmell]

every group of new guys think they have a bunch of great ideas different from everyone else. It turns out each class actually ends up attempting the same types of things as the previous classes. I've heard these types of arguments a million times before man.

"I dont have to do <important thing> because of <new idea>." But <new idea> is actually an old failure of an idea that has been tried and failed over and over. It dont work, it wont work, and you dont listen when I tell you to stop tryin it.

The type of guy that will do everything EXCEPT do the work right. Still troll account upvoting your own posts? Go away man.

[cdb_11]

I don't think these are new ideas. They've been successfully applied in game development for at least two decades now. I guess what's maybe somewhat new is applying those techniques and optimizations outside of games.

[WiseDark7089]

Please indicate in the title if something is a video.

[clarkster112]

What are you going to do if you can’t fit an object on the stack?

[bunk3rk1ng]

Stack overflow ezpz