Source
r/ProgrammingLanguages•
PL_Design

On the merits of low hanging fruit.

Discussion

I've been reading this subreddit for several years now, and so often it bums me out. It seems like almost everyone is obsessed with reaching as high up the fruit tree as they can go, and everyone is trying to grab the exact same fruit. If that were the only fruit left, then I would understand that, but it's really, really not. There's still loads of low hanging fruit just begging to be picked. It would be nice to see a little more variety here, y'know? So here's my contribution:

The past couple of days I've been experimenting with a new global allocator for my personal library for our language. I call it the vspace allocator because its job is to track cells of virtual memory. Right now I'm using 4GB wide cells, and I have roughly 32k of them. The idea here is that when you make an allocation you reserve a cell and mmap some portion of it. Because the nearest mmap will be at least 4GB away you have a strong guarantee that you will be able to mremap up to 4GB of memory in a cell without having to ever unmap and move your data. This means you can build growable data structures without worrying about invalidating ptrs, copying data, or messing around with buckets.

My motivation for building this isn't because I'm expecting people to do all of their allocations through the vspace allocator. No, the use I have in mind is for this to be an allocator allocator. Perhaps "meta-allocator" is a good term for it? Anyway, let me tell you about my ring allocator, which has a fairly unique design:

So in case you're not familiar with them, ring allocators are used as temporary or scratch allocators. They're backed by ring buffers, so once you reach the end of the buffer you will wrap around and start allocating from the beginning of the buffer. Anything that was already there will become clobbered. In theory this is fine because you're not supposed to put any long-lived data into a scratch allocator. In practice this makes calling functions a scary prospect because there may be an arbitrary number of scratch allocations made. My solution to this is to put a pin into the ring allocator with the idea being that any allocation that crosses the pin's index will cause a panic. This way you will be notified that you ran out of scratch memory instead of the program continuing in invalid state. To avoid conflicts over pins multiple ring allocators can be used.

The way pinning works is there can only ever be a single pin, which is fine because a second pin would necessarily be protected by the first pin. When you attempt to make a pin you will receive a boolean that you will use as a key to try to remove the pin later. If the boolean is true, then you are the owner of the pin, and may remove it. If it is false you are not the owner of the pin, and it will not be removed. In this way every function that's interested in pinning some memory that it's using can be a good citizen and attempt to use its key to unpin its memory when it's finished doing its work. A language with macros and defer can create convenient macros that ensure the user will never forget to unpin the ring alllcator.

Now let's combine my ring allocator with my vspace allocator: Instead of panicking when an allocation would cross the pin, the ring allocator can move the pin to the 0 index, grow larger, and then move the allocating head past the old pinned memory and into the newly allocated memory. If excess memory usage is a concern, then an absolute max size can be set, and successfully upinning the ring allocator can shrink it to its original size.

In this way a ring allocator can be made safe and reliable to use. This is notable low hanging fruit because it automates memory management in many of the same ways that a GC does, but with barely any overhead. Of course I'm not suggesting that my ring allocator is sufficient by itself to handle everything about memory management, but it might be an attractive alternative to garbage collection for some tasks.

There are lots of simple ways to attack useful subsets of hard problems, and sometimes that simplicity is so valuable that it's worth settling for an 80% solution instead of holding fast for a 100% solution. I believe being aware of designs like this should inform the way we design our languages.

Posted Jun 2, 2021, 1:47 PM UTC · edited

6648
hum0nx•

I'm curious what you mean by low hanging (compared to high up) fruit. Like high level programming problems? Or like attempting more than what is realistic

22
noogai03•

he probably means stuff like"i'm going to write Rust with Haskell typing!" as high up

28
smasher164•

I do think there is too much mindshare going towards memory safety in PL nowadays. There are so many interesting, under-explored ideas out there.

15
noogai03•

Memory safety as a route to concurrency is a huge deal but for sure it's not the end of the line. What else did you have in mind?

12
oilshell•

For me, it's building distributed systems with dynamic languages. The REPL as a debugger for distributed state (since classic debuggers don't work well for distributed systems)

Type systems also have severe limitations without a single address space, and even more so across a LAN or WAN.

To me the focus on single programs is weird since nearly everything we use is part of a distributed system these days -- all video conferencing, all social media, even many dev tools, many games, etc.

This basically sums up my feelings:

https://twitter.com/jeanqasaur/status/1394804946818650115

Why is it that people get so into linting and type-checking within services, while they're okay letting latent dumpster fires burn across services?

In other words, for the domain of distributed systems, which is extremely large and important now, it's not worth squeezing the last 10% of ergonomics out of a type system. Because anyone who has built them know that they are dumpster fire from a systems perspective. And also that they are composed of OLD languages.

The bigger the distributed system, the more heterogeneous the code. I'd say nearly all interesting systems have some 10- or 20- year old code somewhere. New languages help little unless they are good at interfacing with existing code.

I like Rust, and I understand why it has to be a "clean slate" to some extent (type safety is a global property), but I also feel like it's not great at incorporating existing code, and encourages long-winded rewrites.

27
PL_DesignOP•

Basically this, yeah. There are a lot of extremely abstract ideas going around that have more in common with theorem solving than bit shoveling. I want both to exist, of course, but in the meantime there are lots of people who don't need more than a better shovel.

1
L8_4_Dinner•

I like it. It sounds like a fun data structure to build. Could you post a link?

Good memory management needs a lot of tricks to be done correctly and efficiently. It's not as easy as K&R made it out to be with their bump pointer example of implementing alloc(), with the free() implementation left to the reader! 🤣

14
PL_DesignOP•

I'm currently reworking my ring allocator, so I don't have a functioning example to show right now. I can post my vspace allocator, though:

GIBIBYTE :: s64_1073741824;
PADDING  :: #run: 32 * GIBIBYTE;
STRIDE   :: #run:  4 * GIBIBYTE;

MIN_MAPPABLE_PTR ::= null;
MAX_MAPPABLE_PTR ::= null;

VSPACE :*vspace:= null;

:vspace
{
	size: s64;

	## used to track which virtual address cells are available for new allocations
	head : s64;
	offset_stack: *s64;

	## used to track how much memory has been mmapped in a cell
	cell_sizes: *s64;
}

_init_alloc :: ()
{
	## find the brk, and then use a value on the stack to find the stack
	## the padding and alignment are because of paranoia
	brk: s64 = align(#cast(s64,  find_brk()) + PADDING, PAGE_SIZE);
	stk: s64 =       #cast(s64,        &brk) - PADDING;

	## the number of useful virtual addresses
	mappable_size := align(stk - brk, STRIDE);

	## the first stride holds the vspace allocator's metadata
	count := mappable_size / STRIDE - 1;
	metadata_size := #sizeof_t(s64) * count;
	vsize := #sizeof_t(vspace) + metadata_size + metadata_size;


	MIN_MAPPABLE_PTR = #cast(*diov, brk                );
	MAX_MAPPABLE_PTR = #cast(*diov, brk + mappable_size);


	MIN_MAPPABLE_PTR = mmap_nofail(vsize, MIN_MAPPABLE_PTR, PROT_FLAG.rw, MMAP_FLAG.fixprivanon, FD.invalid, 0);
	layout_of(advance_buffer(STRIDE, MIN_MAPPABLE_PTR));
	##vsize:
	{
		partition( #sizeof_t(vspace) ) =>= VSPACE;
		partition( metadata_size     ) =>= VSPACE.offset_stack;
		partition( metadata_size     ) =>= VSPACE.cell_sizes;
	}
	end_layout();

	VSPACE.size = count;
	VSPACE.head = count;

	## fill the offset stack with offsets to cells
	i := 0;
	while: i != count
	{
		VSPACE.offset_stack @ i = i * STRIDE;
		++i;
	}
};

ptr_to_vspace_offset :: (ptr: *void) -> s64
{
	ptrs64 := #cast(s64,              ptr);
	   min := #cast(s64, MIN_MAPPABLE_PTR);
	   max := #cast(s64, MAX_MAPPABLE_PTR);

	assert_not( (ptrs64 < min) || (ptrs64 >= max) );

	ptrs64 -= min;

	assert( (ptrs64 % STRIDE) == 0 );

	return ptrs64;
};

offset_to_vspace_index :: (offset: s64) -> s64
{
	return offset / STRIDE;
};

ptr_to_vspace_cell_size :: (ptr: *void) -> s64
{
	index := offset_to_vspace_index(ptr_to_vspace_offset(ptr));
	return VSPACE.cell_sizes @ index;
};

allocate_fd :: (size: s64, fd: FD) -> *diov
{
	assert_not( (VSPACE.head == 0) || (size < 0) );

	--VSPACE.head;
	offset := VSPACE.offset_stack @ (VSPACE.head);
	VSPACE.cell_sizes @ offset_to_vspace_index(offset) = size;

	return mmap(size, MIN_MAPPABLE_PTR @+ offset, PROT_FLAG.rw, MMAP_FLAG.fixprivanon, fd, 0);
};

allocate :: (size: s64) -> *diov
{
	return allocate_fd(size, FD.invalid);
};

allocate_t :: (size: s64) T -> *T
{
	return allocate( size * #sizeof_t(T) );
};

resize :: (new_size: s64, ptr: *void) -> bool
{
	offset   := ptr_to_vspace_offset(ptr);
	index    := offset_to_vspace_index(offset);
	old_size := VSPACE.cell_sizes @ index;

	ptr = mremap(old_size, ptr, new_size, ptr, REMAP_FLAG.none);
	if: #cast(s64, ptr) < 0
	{
		return false;
	}

	VSPACE.cell_sizes @ index = new_size;
	return true;
};

resize_t :: (new_size: s64, ptr: *T) T -> bool
{
	return resize( new_size * #sizeof_t(T), ptr );
};

free :: (ptr: *void)
{
	assert_not( VSPACE.head == VSPACE.size );

	offset := ptr_to_vspace_offset(ptr);
	index  := offset_to_vspace_index(offset);
	size   := VSPACE.cell_sizes @ index;

	VSPACE.offset_stack @ (VSPACE.head) = offset;
	++VSPACE.head;

	munmap(size, ptr);
};

I note that my assumptions about how the space between the brk and the stack work aren't necessarily true, and the only reason I can get away with this at all is because I'm not relying on libc, and I'm not using any external libraries. I've had someone tell me that this is likely to blow up in my face once I start using audio or video drivers, so consider this extremely experimental. Someone has suggested I use MAP_NORESERVE to make this less brittle, but I haven't looked into that yet.

If you have questions about the language feel free to ask. The one thing that's most likely to trip you up is the =>= operator, which is a mirror of the = operator: The rvalue goes on the left-hand side, and the lvalue goes on the right-hand side. The reason I did that is because I wanted the partitioning of the buffer to be the first and most visible part of the layout code.

2
[deleted]•

[deleted]

1
mamcx•

Well, I think your fruit is very high :).

I doing my lang in part chasing these low-hanging fruits, some of them (not all implemented yet, but is the idea. My niche is business software so you will see the bias for finance math and data manipulation):

  • Add Decimal as first-class numeric type AND the default
  • Add Date(Time) too, and inmutable with (eventually) noda-like functions
  • If 1+ 1 then go ahead and do [1,2] + 1 = [2,3]
  • The vector type is tensor from the start and allows it to be used like a table(2d).
  • Instead of functional chaining of map/fold/etc AND LINQ-like select, filter, only do LINQ-like (that in the inside is - map/fold/etc)
  • Built-in support for a variety of protocols, formats, and data transformation (inspired by serde, I will provide in-built machinery to do this so the user only need to provide the mappings). This means no more:

​

data LoginForm do
   user..
   pwd..

data LoginRowInDb do
   user..
   pwd..
fun copy(form:LoginForm):LoginRowInDb do
  let row = LoginRowInDb()
  row.user = form.user
  ...
//Instead:
let row =LoginRowInDb(..form) //the lang auto-do this
// Copy with transform
let row =LoginRowInDb(..form?select lower(.user) as user, ...))
  • Error/Exceptions have diagnostic data!:

​

data Error do
 msg:Str
 entity:Option<Str>
 cause:Option<Str>
 source:Option<Str>

raise Error("FileNotFound", entity=Some("file.txt"), source=Some("ReportModule")
  • Assert are first-class validations:

​

assert Eq(A,B, A==B, error=Error(...)

fun pwd_check(a,b)
  checks:
     assert Eq(a,b)
do
   ...///extra code

//in caller
 match pwd_check(form.pwd, user.pwd)
Ok(-)
Err(Assert(err)) do
  return ValidationError(err)

and stuff like that

13
L8_4_Dinner•
  • Add Decimal as first-class numeric type AND the default
  • Add Date(Time) too, and inmutable with (eventually) noda-like functions
  • If 1+ 1 then go ahead and do [1,2] + 1 = [2,3]
  • The vector type is tensor from the start and allows it to be used like a table(2d).

I like these choices (probably because we made the same ones!)

6
mamcx•

Great minds think alike :)

P.D: Link to the lang?

3
L8_4_Dinner•

blog: xtclang.blogspot.com/

repo: https://github.com/xtclang/xvm

3
PL_DesignOP•

Well, I think your fruit is very high :).

Yeah, I might be reaching higher than I think I am.

Add Decimal as first-class numeric type AND the default

You've reminded me that I really, really, really want fixed point arithmetic support so I can avoid using IEEE floats.

1
ipe369•

everyone is trying to grab the exact same fruit

what fruit is this? sounds juicy

12
Netzapper•

I expect they mean (nearly) pure functional or procedural with fancy abstract algebra of types.

7
jhi•

Severe case of Haskellitis?

7
Felicia_Svilling•

That seems pretty low hanging to me..

-1
hou32hou•

Thanks, I think I’ve been one of them trying to make the perfect language, deep down I understand that it’s impossible, but yet I don’t want to compromise, ah so contradictory,

9
PL_DesignOP•

I'm not suggesting that you should stop pursuing perfection, but in the mean while there is definitely value in searching for "good enough" solutions. If nothing else it can help you bootstrap yourself up to where you want to be.

3
ArrogantlyChemical•

Gotta be honest with you, I have no what all that means.

5
PL_DesignOP•

Ah, that's alright. I might be reaching up higher than I think I am.

2
cxzuk•

I believe that allocators and the framework to compose and utilise them are mission critical to procedural languages. Its my believe they are a system property (non-functional requirements), that cut across your algorithms - And should even have language level support.

I find both your allocators interesting, Im going to have a see into their properties at some point. I understand allocations are typically for heap objects - You've mentioned function calls etc - The pin idea feels to me at present that it would just decompose to become a stack allocator. If head-end objects could really be overwritten, Im not sure why you wouldn't do so before the function call.

I look forward to investigating more, keep on coding ✌

2
PL_DesignOP•

I'm not sure I agree that allocators should have specialized language-level support. The reason why I say this is because they're just normal functions and data structures. The point of having a programming language is exactly to make it easy to write functions and data structures, so anything that would make allocators easier to write should just be available as a general tool. If you're talking about something like Jai's/Odin's implicit context system, then I'm also not a fan. When I used Odin I always felt like it introduced more uncertainty than it ever helped me. Maybe you have an idea I haven't considered yet, though, so I might be putting my foot in my mouth here.

But yes, I do agree that more research into allocation strategies is mission critical for procedural languages.

When the ring allocator is pinned it does just act like a more complex growable bump arena. It might ultimately be better to just use a growable bump arena in the first place, but I do like the option of just letting the ring buffer cycle so I don't need to worry about freeing anything or resetting the bump arena.

1
Pavel_Vozenilek•

It should be easy to replace allocators. For example, every test could automatically verify there are not leaks happening inside. I implemented such a thing in C and it did wonders in keeping leaks down. The allocator also checked against buffer overflow & underflow, use-after-delete and alignement problems. It was two orders of magnitude larger than typical toy allocators, but it was worth the effort.

2
PL_DesignOP•

Not all allocator designs can trivially be swapped for other allocator designs. Growable arrays, stacks, sets, and hashmaps are particularly dramatic examples. You could potentially argue that they're not allocators, but the most reliable way to implement them is as though they were allocators. If you implement them as consumers of some general purpose allocator API, then you're going to run into weird problems. To see what I mean try using Odin's hashmap type with its temporary allocator. Bump arenas and ring allocators also don't fit the bill for a generic allocator API because they don't have a concept of freeing individual pieces of memory, and variations of these allocators can have unique features. For example, see my pinnable ring allocator.

To do what you're talking about you would need to write debug versions of the allocators you're using. You couldn't just swap to a general purpose debug allocator and expect to get a good results. What you're talking about is a good idea, but I don't think it needs any special support. It's just conditional compilation.

To reiterate my point here because I think this is important: I very much dislike the idea of general purpose allocator APIs. I think they get in the way and introduce too many moving parts to something that needs to be as simple and reliable as possible.

1
Pavel_Vozenilek•

My allocator interface looked like this:

struct allocator
{
  // Mandatory part
  void* (*allocate)(uint sz); // 8 bytes aligned
  // size of the block was needed in one corner case
  // and it was also used as an additional safety check
  void (*deallocate)(void* p, uint sz); 

  // Optional part, ptrs could be null
   ... other aligned allocs
   ... in place realloc
   ... bulk allocs
   ... bulk deallocate
   ... handing thread unsafe allocator between the threads
   ... collecting statistics
};

As a base I used Doug Lea's allocator ( http://gee.cs.oswego.edu/dl/html/malloc.html ), which has very rich API.

I implemented:

  • traditional block allocator (using Doug Lea's library)
  • block allocator where deallocate was no-op and all memory was released when allocator was destroyed (also feature of the library)
  • the above had both thread safe and thread unsafe variants (with checking against misuse)

I also implemented bump allocator (I think this is how it is called). This one was always thread unsafe (no need to have threaded version), deallocate was always no-op. It could use provided stack memory. When its current block was exhausted, it allocated a new one.

There was lot of parametrization for the variants of allocators. The code was full of debug checks.

It allowed me to swap allocators easily, w/o need to modify the code. Internal checking ensured I didn't leak accidentally.

1
Pavel_Vozenilek•

I'm not sure I agree that allocators should have specialized language-level support.

One (relatively) minor feature could be useful: compiler providing readable stack traces. In my allocators, I initially wanted to store full stack trace for every allocation, to identify leaks faster. I used helper C macros inside every function, but it was so clumsy and annoying that I dropped it all. If compiler provided such stack traces, invisibly and reasonably efficiently, I'd use them.

It wouldn't be feature to boast about, but handy for some situations, where the leak is too hard to spot, or where there's no debugger.

1
PL_DesignOP•

I've been thinking about how to write a fuzzer for my language, and what seems to make the most sense is to have macros that get automatically expanded at the top and bottom of each function, except for functions with a #no_instrument directive. By convention it should be expected that no business logic is to go in these macros because they're for runtime metadata purposes only. This way it's easy to instrument code so you can accumulate things like stack traces and profiling data, and you wouldn't need to worry about a library trampling whatever instrumentation you've got.

1
slaymaker1907•

One thing I've wanted to explore is pluggable structure exploration. Knowing the structure of objects is super useful for frameworks letting you do stuff like equality, hashing, serialization, conversions, and even unification for a minikanren library.

2
PL_DesignOP•

Introspection is a super cool way to make a language more powerful without adding much complexity.

1
moon-chilledbonsai•

I must say, I find this a rather bizarre sentiment.

I don't need a better shovel! My shed is full of lovely shovels, and though I might be able to make something a tiny bit more convenient for myself to use, it's not really a practical use of time. And ultimately, implementing a novel GC algorithm is a lot more interesting than making yet another growable ring buffer.

(Well, ok, maybe not gc specifically—I hate allocators—but you get the point.)

2
PL_DesignOP•

I'm less interested in whether something is interesting and far more interested in whether something is useful or practical.

1
7Geordi•

Not gonna lie, all this got me thinking about was how to model memory, allocation, lifetimes, borrowing, transactions, etc in the type system...

Damn your low hanging fruit!

2
PL_DesignOP•

There's value in that. I just want people to be considering other approaches, too.

1
McCoovy•

It bums you out that people don't set their sights lower? I can't identify with your complaint at all.

1
PL_DesignOP•

You are free to deliberately misinterpret what I said.

2
McCoovy•

I've been reading this subreddit for several years now, and so often it bums me out. It seems like almost everyone is obsessed with reaching as high up the fruit tree as they can go, and everyone is trying to grab the exact same fruit. If that were the only fruit left, then I would understand that, but it's really, really not. There's still loads of low hanging fruit just begging to be picked. It would be nice to see a little more variety here, y'know? So here's my contribution:

That's what you said.

I don't feel as though I've misinterpreted it. If there was a choice between people solving hard problems and people solving easy problems then i prefer they solve the hard problems. Low hanging fruit is what industry is for. That's where inefficiencies get ironed out. Theorists and designers aren't going to make their passion project low hanging fruit.

It's completely unclear what you mean by low hanging fruit. Do you mean beginner problems? When beginners post here they immediately get pointed to learning resources. It turns out there isn't much discussion to he had there until they've done their homework. do you mean common problems with low complexity? That's a matter for documentation and more teaching resources, not discussion. There just isn't any interesting, informative discussion to have about the same repetitive, simple topics. The only thing to is point them to an article where all of the discussion has already been exhausted.

Your problem isn't beginner, common, or low complexity so i have no idea what you're asking for or why.

2
PL_DesignOP•

Consider the case of a borrow checker, a garbage collector, and batch allocators. They don't all solve the same problems, but a large majority of their problems do intersect. The first two are heavy solutions, and they typically require heavy tooling to work. You have to stretch and reach high to grasp these things. Batch allocators, on the other hand, are simple and require little from a language except the ability to work with raw ptrs. They're quite possibly already in your hand.

Consider the case of templates vs. void*s. If full template metaprogramming isn't necessary for the problems you're trying to solve, then void* becomes an attractive solution because it doesn't introduce any extra complications in the compiler.

Consider the case of C++ references vs. reading through ptrs like Go can. Of course C++ references are about more than just eliminating the need for the -> operator, and because of legacy reasons C++ can't just change how the . operator works, but from a day-to-day "let's make programming not suck" point of view that's one of the most important things about them. Go just does the simple thing, and it's good.

Consider the case of exceptions vs. multiple return. While if err != nil can be noisy, it's also simpler and gives you stronger guarantees about when, how, and why you will exit a function, and multiple return is just generally useful. Exceptions are significantly more complex, and come with a lot of downsides.

Consider the case of inheritance polymorphism vs. tagged unions.

Consider the case of retained mode vs. immediate mode GUI libraries.

Consider the case of ropes vs. gap buffers.

Consider the case of shift-reduce vs recursive descent parsers.

What I'm talking about here is complex vs. simple designs. I'm not going to say that all complex designs are inappropriate, but I am going to say that simplicity is almost always a virtue. Read the last paragraph of my post:

There are lots of simple ways to attack useful subsets of hard problems, and sometimes that simplicity is so valuable that it's worth settling for an 80% solution instead of holding fast for a 100% solution. I believe being aware of designs like this should inform the way we design our languages.

This is about how we build our compilers. This is about the runtime assumptions we make about our languages. This is about the tools we provide for our users, and looking for sensible ways to solve the problems they actually have. Pawning these things off on "industry" is not an acceptable attitude to have here. If you don't care about the needs of the people using your product, then you're not a designer. You're just a hobbyist, and I couldn't care less about your passion project.

1
ArrogantlyChemical•

I feel like on one hand you're saying you would choose a solution because it's easier to implement even though it's an 80 percent solution, while on the other hand saying the goal should be user ergonomics. These two contradict each other.

You argue for gos awfull err is nill check hell and against well implemented exceptions (that would require you to handle them like in java), then that is not user friendly at all.

Or this. "Consider the case of templates vs. voids. If full template metaprogramming isn't necessary for the problems you're trying to solve, then void becomes an attractive solution because it doesn't introduce any extra complications in the compiler."

Whether or not a compiler is more complex is not something that impacts user friendliness. If a more complex compiler can make the language more user friendly (for example, for all the people who do need templates now or at some point in the future) then that is good.

I also don't agree that recursive descend is easier than shift reduce but whatever.

2