Here's a problem I've seen a lot (it's probably classified as an "Antipattern" or a "Code Smell" and as such has a name in the appropriate circles, but I wouldn't know, so I'll leave it nameless).
You have some kind of data structure that you pass around a lot. Soon, the most valuable thing about the structure isn't the data it keeps, but the fact that it's available all the way through some hairy flow of control. If you want to have your data flow through all those pipes, just add it to The Data Structure. (To antipattern classification enthusiasts: I don't think we have a god object yet because we really want to pass our data through that flow and it's right to have one kind of structure for that and not, say, propagating N+1 function parameters.)
Now suppose the structure holds an open set of data. For example, a spam filter could have a data structure to which various passes add various cues they extract from the message, and other passes can access those cues. We don't want the structure to know what passes exist and what cues they extract, so that you can add a pass without changing the structure.
I don't think there's a good way to do it in a 3GL. In C or C++, you can:
- Aggregate the cue structures by value (which means you have to recompile everything once you change/add/remove a member from any of them)
- Keep pointers to the cue structures and use forward declarations to avoid recompilation (a bit slower, and you still have to recompile when you add/remove a whole cue structure)
- Keep an array of void* or base class objects (not debugger-friendly, and requires a registration procedure to resize the arrays according to the number of passes and deal dynamically computed indexes to the cues to all who wish to access them)
- Keep a key -> void* map (increasingly slow and debugger-unfriendly, and you need registration to compute the keys from cue names, or use the C substitute for interning – use pointers to global variables with names like &g_my_cue_key as keys)
- Keep a string -> void* map (no registration or pseudo-interning, but really slow)
On top of JVM or .NET, you have pretty much the same options, plus the option to generate the cue container structure dynamically. Each cue would define an interface and the container structure would implement all those interfaces. The debugger would display containers nicely, and the code accessing them wouldn't depend on the container class. I'd guess nobody does that though because the class generation part is likely somewhat gnarly.
In a 4GL, you can add attributes to class objects at run time. This is similar to keeping a key->pointer map in a 3GL, except the name interning is handled by the system as it should, and you don't confuse debuggers because you're using a standard feature of the object system. Which solves everything except for the speed issue, which is of course dwarfed by other 4GL speed issues.
Now, I used to think of it as one of the usual speed vs convenience trade-offs, but I no longer think it is, because a struct linker could solve it.
Suppose you could have "distributed" struct/class definitions in an offset-based language; you could write "dstruct SpamCues { ViagraCue viagra; CialisCue cialis; }" in the Medication spam filter module, and "dstruct SpamCues { FallicSymbolsCue fallic; SizeDescriptionsCue size; }" in the Penis Enlargement module. The structure is thus defined by all modules linked into the application.
When someone gets a SpamCues structure and accesses cues.viagra, the compiler generates a load-from-pointer-with-offset instruction – for example, in MIPS assembly it's spelled "lw offset(ptrreg)". However, the offset would be left for the linker to resolve, just the way it's done today for pointers in "move reg, globalobjectlabel" and "jump globalfunclabel".
This way, access to "distributed" structures would be as fast as "normal" structures. And you would preserve most optimizations related to adjacent offsets. For example, if your machine supports multiple loads, so a rectangle structure with 4 int members can be loaded to 4 registers with "ldm rectptrreg,{R0-R4}" or something, it could still be done because the compiler would know that the 4 members are adjacent; the only unknown thing would be the offset of the rectangle inside the larger struct.
One issue the linker could have on some architectures is handling very large offsets that don't fit into the instruction encoding of load-from-pointer-with-offset forms. Well, I'd live even with the dumbest solution where you always waste an instruction to increment a pointer in case the offset is too large. And then you could probably do better than that, similarly to the way "far calls" (calls to functions at addresses too far from the point of call for the offset to fit into 28 bits or whatever the branch offset encoding size is on your machine) are handled today.
The whole thing can fail in presence of dynamic loading during program run as in dlopen/LoadLibrary; if you already have objects of the structure, and your language doesn't support relocation because of using native pointers, then the dynamically loaded module won't be able to add members to a dstruct since it can't update the existing objects. Well, I can live with that limitation.
If the language generates native object files, there's the problem of maintaining compatibility with the object file format. I think this could "almost" be done, by mapping a distributed structure to a custom section .dstruct.SpamCues, and implementing members (viagra, cialis, fallic, size) as global objects in that section. Then if an equivalent of a linker script says that the base address of .dstruct.SpamCues is 0, then &viagra will resolve to the offset of the member inside the structure. The change to automatically map sections named .dstruct.* to 0 surely isn't more complicated than the handling of stuff like .gnu.linkonce, inflicted upon us by the idiocy of C++ templates and the likes of them.
And here's why I'll probably never see a struct linker:
- If the language uses a native linker, a small change must be done to that linker in order to handle encodings of load/store instructions in ways it previously didn't (currently it only has to deal with resolving pointers, not offsets). Since it's platform-specific, the small change is actually quite large.
- You could compromise and avoid that change by generating less efficient code which uses the already available linker ability to resolve the "address" of the viagra object in the zero-based .dstruct.SpamCues section – the code can add that "address" (offset, really) to &cues. But that could still force changes in the compiler back-end because now it has to generate assembly code adding what looks like 2 addresses, which makes no sense today and might be unsupported if the back-end preserves type information.
- The previous items assume that the portable "front-end" work to support something like dstruct isn't a big deal. However, I'd guess that not enough people would benefit from it/realize they'd benefit from it to make it appear in a mainstream language and its front-ends.
- I could roll my own compiler to a language similar to a mainstream one, with a bunch of additions like this struct linker thingie. Two problems with this. One – it's too hard to parse all the crud in a mainstream language (even if it isn't C++) to make it worth the trouble, unless your compiler does something really grand; a bunch of nice features probably aren't worth it. Two – most programmers take a losing approach towards their career where they want to put mainstream languages on their resume so that losers at the other end can scan their resumes for those languages; if your code is spelled in a dialect, you'll scare off the losers forming the backbone of our industry.
It still amazes me how what really matters isn't what can be done, but what's already done. It's easier to change goddamn hardware than it is to change "software infrastructure" like languages, software tools, APIs, protocols and all kinds of that shit. I mean, here we have something that's possible and even easy to do, and yet completely impractical.
Guess I'll have to roll my own yet-another-distributed-reflective-registration bullshit. Oh well.
80 comments ↓
Protocol buffers achieve something very similar in distributed systems — after adding a field, you only need to recompile the binaries that access the field.
Using the protocol-buffer extension mechanism you don't need to declare all the fields in one place. If the components of your system are rather coarse grained, then serializing/deserializing within the binary may make sense.
By "within the binary", do you mean that in the spam filter example, the cue container would be passed in encoded form, deserialized by each pass and serialized back if cues are added?
Also, are you talking about a specific implementation of "protocol buffers" or a general concept? Googling for "protocol buffer" yields way too many results, the first one being, well, Google's implementation of serialization that allows the format to be changed over time; however, I didn't see anything related to distributed format definition.
I'm a bit confused by two of your points. You say:
Aggregate the cue structures by value (which means you have to recompile everything once you change/add/remove a member from any of them)
And later on:
I could roll my own compiler to a language similar to a mainstream one, with a bunch of additions like this struct linker thingie.
Doesn't the latter comment mean you essentially want to only implement a front end to your language? If so probably you might have to recompile/preprocess all the code anyways?
I feel the following standardized features in a language (D I'm looking at you) would solve a lot of such complex problems:
1) Macros that can manipulate the AST at compile time
2) Support for run-time compilation/optimization (most of this might be in the standard library).
If the debugger can be made aware of these it would be great.
Well, I could have my front-end use linker features like custom sections via pragmas, and then I wouldn't even need to generate assembly, just C with platform-specific pragmas and a linker script.
Regarding AST manipulation – I think the D approach of compiling strings into the code with mixin(string) is about as good as you can get in a hairy pop infix language in terms of meta-programming, because working at the AST level means exposure to a gnarly object model. As to run time compilation, it means a larger system; on desktop, I definitely don't mind, on the other hand, I can and do generate C at run time on the desktop today – save to a file, run gcc, then dlopen. And on systems where I can't install gcc I also lack the space to carry the hairy compiler for a pop infix language.
In short, I think that in order to be as strong at metaprogramming as Lisp or Forth, you have to be Lisp or Forth – that is, make ASTs very simple.
Wait a second.
A struct linker is essentially a recompiler if you don't want performance to suffer — e.g., there's different opcodes for accessing a register + 8 bit offset and +32 bit offset. Once enough fields are added, codes and relative jumps will need to be rearranged to the point of killing optimization.
What's the problem with compiling when you make a change again? Being fond of plain C as you are (and I am in that camp too), you could just use a quick C compiler such as Fabrice Bellard's tcc and be done with it. 10 secs for cold booting a complete linux kernel from _source_ is good enough for me.
Regarding "recompiler" – as I said, I don't mind the sliiiiiight performance hit from having the compiler always generate the wasteful kind of load/store just in case the offset turns out huge; then the linker can always do its thing no matter what the offset turned out to be – unless there exists a machine so insane that you can't implement load-from-small-offset using the encoding you normally use for load-from-large-offset. Now that would be quite amazing.
Another option is to do it the way automatic "far call patching" is done by some linkers – when you branch too far for the offset to fit into the 26 or whatever number of bits the branch command encoding gives you, they generate code branching to a trampoline. So here if the linker saw huge offsets, you could branch to code doing the load/store and then branch back. Now, I don't know how they manage linkage with this feature because the trampoline code must be close to the function calling it, and that moves other functions which in turn may cause the generation of trampolines, etc.; looks like one of those problems where linkage ought to "converge" in multiple passes. I dunno if they limit the number of passes or overallocate space or…, just that it works (say, in Green Hills C++ on MIPS). But as I said, I can live with "always assume large offsets", so this mess is largely irrelevant.
Regarding motivation: yeah, I like C, I just get to work with C++. Sucks, doesn't it? Now, the other thing that could motivate you in saner compiled languages is that you might work with compiled code not available in source form, or be compatible with an existing build, and add members to structs they use; there are good use cases for that when the compiled code is basically this pipe you want your data to be going through. Say, you're a spam filter plugin and the compiled code is that spam filter core engine. Or something.
For the case of passing state through complex call chains extensibly, there's a nice mechanism in Scheme called "parameters" – see http://srfi.schemers.org/srfi-39/srfi-39.html – that's what us smug Lisp weenies use!
I consider something really special in this site.
Just wanna input on few general things, The website layout is perfect, the articles is very superb : D.
You got yourself a new rader.
I like, will read more. Thanks!
Enjoyed reading through this, very good stuff, thankyou .
I conceive this web site holds some real superb information for everyone : D.
Nice post. I was checking continuously this blog and I am impressed!
Very helpful information specially the last part :)
I care for such information much. I was looking
for this certain information for a very long time.
Thank you and best of luck.
Enjoyed reading through this, very good stuff, thankyou .
You got yourself a new rader.
I read this paragraph fully regarding the resemblance of
hottest and previous technologies, it's remarkable
article.
Yeah bookmaking this wasn’t a risky decision outstanding post! .
I was recommended this website by my cousin. I am not sure whether this post is written by him as
no one else know such detailed about my
trouble. You're amazing! Thanks!
This is a really good tip particularly to those new to the blogosphere.
Brief but very accurate information… Appreciate your
sharing this one. A must read post!
Thanks for some other excellent article. Where else may just anybody get that kind of info in such an ideal approach
of writing? I've a presentation subsequent week, and I am at the
search for such info.
Having read this I believed it was extremely informative.
I appreciate you spending some time and effort to put this informative article together.
I once again find myself spending way too much time
both reading and posting comments. But so what, it was still worthwhile!
You made some good points there. I looked on the web for additional information about
the issue and found most individuals will go along with your views
on this web site.
Your way of explaining the whole thing in this post is genuinely nice,
all can without difficulty know it, Thanks a lot.
I really like what you guys tend to be up too. This sort of clever work and coverage!
Keep up the terrific works guys I've included you guys to my blogroll.
Howdy! Quick question that's completely off topic. Do you know
how to make your site mobile friendly? My web site looks weird when viewing from my iphone
4. I'm trying to find a theme or plugin that might be able to resolve this issue.
If you have any suggestions, please share. Thank you!
Appreciate this post. Let me try it out.
Good day! I could have sworn I've visited this
web site before but after browsing through many of the posts
I realized it's new to me. Nonetheless, I'm certainly delighted I stumbled upon it and I'll be book-marking it and
checking back often!
This is very fascinating, You're an overly skilled blogger.
I have joined your rss feed and look ahead to in quest of more of your magnificent post.
Also, I have shared your website in my social
networks
I do think various web site keepers must take this website
as a possible model type, pretty neat very good convenient to use pattern, besides the subject
matter. You are an knowledgeable in this field!
Thanks in favor of sharing such a pleasant idea, article
is good, thats why i have read it completely
Thanks a lot for sharing this with all people you actually recognize what you're
speaking approximately! Bookmarked. Please also consult with my site =).
We will have a hyperlink change agreement among us
Hi there! This is my first visit to your blog! We are a group of volunteers and
starting a new project in a community in the same niche.
Your blog provided us beneficial information to work on. You have done a outstanding job!
It's in reality a great and helpful piece of info.
I am happy that you shared this useful information with us.
Please stay us up to date like this. Thanks for sharing.
You got yourself a new rader.
Thank You for this.
Hey, glad that i found on this in google. Thanks!
I am not rattling great with English but I get hold this really easygoing to read .
Ahaa, its nice dialogue about this article at this place at this web site, I have read all that, so now me
also commenting here.
Keep on working, great job!
Just wanna input on few general things, The website layout is perfect, the articles is very superb : D.
I really enjoy examining on this page , it has got good goodies .
Respect to website author , some wonderful entropy.
Respect to website author , some wonderful entropy.
I conceive you have mentioned some very interesting details , appreciate it for the post.
Very interesting points you have remarked, appreciate it for putting up.
We stumbled over here coming from a different page and thought I may as well check things out.
I like what I see so i am just following you. Look forward to looking into your web page
yet again.
Amazing website. Loads of effective details below.
My organization is providing the application to several friends ans moreover sharing throughout delectable.
And obviously, thanks a lot for your work!
Hello! I'm at work surfing around your blog from my
new iphone! Just wanted to say I love reading your blog and look forward to all your
posts! Keep up the superb work!
Parasite backlink SEO works well :)
I am glad to be one of the visitors on this great website (:, appreciate it for posting .
Heya excellent web page!! Fellow .. Delightful .. Wonderful ..
I’ll bookmark your blog and then use the enters additionally¡KI’m prepared to come across a multitude of valuable information throughout all
the place, weight reduction figure out extra systems for this
reverence, appreciate your spreading. . . . . .
Awesome, superb web page format! The length have you been running a blog pertaining to?
you get blogs look convenient. All around look of your website is
outstanding, in addition to article content!
I conceive you have mentioned some very interesting details , appreciate it for the post.
Howdy. Today choosing live messenger. This is a effectively published document.
I’ll don't forget to search for it can be found time for keep reading with the handy information and facts.
Information publish. I am going to certainly return.
I like this site because so much useful stuff on here : D.
I have been vanished for a long time, the difference is Walking
out to the key reason why I used to really like this web page.
With thanks , Let me make sure to come back on a regular
basis. Offer you have more website?
Doesn't really matter if someone actively seeks his expected detail, subsequently he/sheneeds to be shown in which intimately, guaranteeing that element is without a doubt managed right here.
Hello, I enjoy reading through your article. I wanted to write a little comment
to support you.
exceptional set up, very educational. I’m thinking about how come another specialists about this world do not
understand it. One should maintain ones publishing.
I'm sure, you’ve a substantial readers’ structure actually!
You have got observed very significant details ! ps decent blog.
“We merely rob yourself if we generate exposes
to the dead.” by just Publilius Syrus.
Write more, thats all I have to say. Literally, it seems as though you relied
on the video to make your point. You definitely know
what youre talking about, why throw away your
intelligence on just posting videos to your weblog when you could be
giving us something enlightening to read?
I don’t even know by domain flipping been for a while there, but I consideration this particular article appeared to be wonderful.
When i don’t are aware of who you really are nonetheless
undeniably you’re attending a famous weblog writer just so without a doubt ??
Thanks a lot!
Skyking, Skyking, this message is your next bit of info. Feel free to contact the agency at your earliest convenience. No further information until next transmission. This is broadcast #6017. Do not delete.
This post is genuinely a nice one it helps new the web viewers, who are wishing in favor of blogging.
This site truly has all of the information and facts I wanted about this subject and
didn't know who to ask.
This site was… how do you say it? Relevant!!
Finally I've found something which helped me.
Many thanks!
It's appropriate time to make some plans for the longer term and it is time to be happy.
I have read this post and if I may I wish to suggest
you some attention-grabbing issues or advice.
Maybe you could write subsequent articles regarding this article.
I want to read more issues about it! plenty of fish natalielise
I have been exploring for a little bit for any high-quality
articles or weblog posts in this sort of house . Exploring in Yahoo I finally stumbled upon this web site.
Studying this information So i am satisfied to show that I've
a very excellent uncanny feeling I found out exactly what I needed.
I most indisputably will make sure to don?t overlook this
website and give it a look regularly.
I simply must tell you that you have an excellent and unique post that I must say enjoyed reading.
You made a variety of ok areas right now there. I did a
search about the difficulty determined a great many men and women have a
similar opinion with your site.
Hey! This post could not be written any better! Reading this post reminds me of my old room mate!
He always kept chatting about this. I will forward
this write-up to him. Fairly certain he will have
a good read. Thanks for sharing!
I must say, as a lot as I enjoyed reading what you had to say, I couldnt help but lose interest after a while.
Helpful information. Lucky all of us I stumbled upon your website accidentally, and
additionally I’m shocked the reasons why this particular collision do not came into
being upfront! My spouse and i saved to fav that.
It’s specialist to build quite a few designs for the future and it's also time for you to be very glad.
I’ve read this post and when I should have That i choose to recommend anyone various unique factors or perhaps hints.
You may will be able to compose future content pieces referring to this text.
I have to find out more reasons for having them!
Cheers, here from google, me enjoyng this, I come back again.
Be grateful for any clever evaluate. Me & my favorite friend ended up solely getting be diligent about this.
We got a new pick up a book in our local assortment however suppose I just perfected clearer because of
this write-up. We are fairly relieved to witness these sort
of spectacular data appearing revealed unreservedly you
can get.
You made a few alright things at this time there.
I conducted looking over the situation identified a good number of folks will have a
similar feeling with the website.
I truly enjoy looking through on this web site , it holds superb content .
whoah that weblog might be fantastic i adore learning your site.
Sustain the wonderful drawings! You realize, a
large amount of humans feel the need round of golf
to do this information, you might enable them all vastly.