问:
Can encapsulation be implemented by proper types rather than accessors?
Interesting question came up while designing interfaces at work, now resolved, but I want to ask about the theory behind it.

Is it incorrect to say that properly typed data members of a class provide encapsulation? (e.g. a Boost Units type that has conversions well defined between other like units, not a typedef'd/boxed uint64_t)

```<code>struct Ruler
{
    Length length;
    Length tick_size;

    Ruler(Length length, Length tick_size);
    // Why not have helpers immediately related to the class, let's
    // stick in an alternative constructor
    Ruler(Length length, int number_ticks);

    // Accessors for # tick marks, because it needs transformed
    // to/from length and tick_size
    int GetNumberTicks(void);
    // This specific example breaks down with this function,
    // but I don't think it's an inherent issue with the design.
    // I need an overload so it will know which of the two member
    // variables to calculate... problem is both are Length
    void SetNumberTicks(int nticks);
}
</code>```

vs

```<code>struct Ruler
{
    Ruler(Length length, Length tick_size);
    Ruler(Length length, int number_ticks);

    // General accessors
    Length GetLength(void);
    void SetLength(Length length);

    Length GetTickSize(void);
    void SetTickSize(Length length);

    // Calculated accessors, see above
    int GetNumberTicks(void);
    void SetNumberTicks(int nticks);

private:
    Length length;
    Length tick_size;
}
</code>```

IMO the first encourages cleaner design by consumers and doesn't encourage pulling in slightly related, but probably attached to the wrong object member functions (eg CanMachineCreateRuler() ). I don't really have the words to describe this properly and I may be misunderstanding the additional utility that the accessors/private data combination provide.

答:
I don't really have the words to describe this properly and I may be
  misunderstanding the additional utility that the accessors/private
  data combination provide.

Let's say that tick size should never be zero, as GetNumberTicks would have a divide by zero issue.

Now, can we generalize this to say that Length should never be zero, allowing us to perform the check inside of Length itself, or is this specific to the context of a Ruler? The answer should be obvious.

This is one of the reasons why accessors are often needed even if you have rich data types that don't expose raw state, e.g. They need that contextual, site-specific information (Ruler-specific info here). They often need to consider the invariants maintained by the outer class (Ruler), and possibly even the interaction of multiple data members (ex: "this Length should never be bigger than this other Length in this class").

A single, scalar-type field often lacks sufficient information to provide the most meaningful accessors/mutators. We often need the contextual info of the class aggregating these fields.

Another reason is this: let's say you find a new way to represent Length which is half the size (making Ruler more cache-friendly with no loss of needed information) but you have 10,000 places in your code that depended on that GetLength accessor. The new type is more efficient, but can easily be converted to/from Length on demand. In this case, thankfully you can more easily apply this under the hood optimization to the private fields of Ruler without rewriting 10,000 lines of code because of GetLength/SetLength. If you exposed the Length fields publicly, you would have to rewrite all 10,000 lines of code to make this change.

Now I'm personally more of a C-style implementor and C++-style interface designer, so for something like this, I'd often just go with this (warning: not recommended for most):

```<code>struct Ruler
{
    Length length;
    Length tick_size;
};
</code>```

... it's like whatever, I don't care about utmost safety here since I'd probably use this thing in some much more complex outer context which can impose the safety checks. I'll then do a lot of testing on the places where Ruler is used. This is unless Ruler was more than a localized implementation detail and had a large number of efferent couplings (in which case I might do the full-blown private fields and getter/setter style design with at least safety assertions to check to make sure tick_size isn't zero in both constructor and setter).

But this is why accessors are important in an outer aggregate like Ruler even if its individual fields also provide accessors.

Also, just a small FYI, but your Get* member functions could benefit from some const-correctness.

Body:
I don't really have the words to describe this properly and I may be
  misunderstanding the additional utility that the accessors/private
  data combination provide.

Let's say that tick size should never be zero, as GetNumberTicks would have a divide by zero issue.

Now, can we generalize this to say that Length should never be zero, allowing us to perform the check inside of Length itself, or is this specific to the context of a Ruler? The answer should be obvious.

This is one of the reasons why accessors are often needed even if you have rich data types that don't expose raw state, e.g. They need that contextual, site-specific information (Ruler-specific info here). They often need to consider the invariants maintained by the outer class (Ruler), and possibly even the interaction of multiple data members (ex: "this Length should never be bigger than this other Length in this class").

A single, scalar-type field often lacks sufficient information to provide the most meaningful accessors/mutators. We often need the contextual info of the class aggregating these fields.

Another reason is this: let's say you find a new way to represent Length which is half the size (making Ruler more cache-friendly with no loss of needed information) but you have 10,000 places in your code that depended on that GetLength accessor. The new type is more efficient, but can easily be converted to/from Length on demand. In this case, thankfully you can more easily apply this under the hood optimization to the private fields of Ruler without rewriting 10,000 lines of code because of GetLength/SetLength. If you exposed the Length fields publicly, you would have to rewrite all 10,000 lines of code to make this change.

Now I'm personally more of a C-style implementor and C++-style interface designer, so for something like this, I'd often just go with this (warning: not recommended for most):

struct Ruler
{
    Length length;
    Length tick_size;
};

... it's like whatever, I don't care about utmost safety here since I'd probably use this thing in some much more complex outer context which can impose the safety checks. I'll then do a lot of testing on the places where Ruler is used. This is unless Ruler was more than a localized implementation detail and had a large number of efferent couplings (in which case I might do the full-blown private fields and getter/setter style design with at least safety assertions to check to make sure tick_size isn't zero in both constructor and setter).

But this is why accessors are important in an outer aggregate like Ruler even if its individual fields also provide accessors.

Also, just a small FYI, but your Get* member functions could benefit from some const-correctness.


答:
Too many accessors are a code smell. They can mean one of two things:

Modeling of data instead of behavior: There are cases where this is adequate. However, I believe you should be honest about it when you are modeling data: just use public members in this case.

Failure to abstract: Ideally every member function should actually do something valuable. It should abstract away from the details how the class is implemented (what data members it uses), and provide some higher level functionality that is actually required by the user.

Providing only simple accessors leaves all the logic that work on its data in the calling code. This is as much a violation of the encapsulation principle as public data members.

Simple getters may be a good idea, because they provide read-only access to their data member. But once you have both a trivial setter and a trivial getter, you know that something's wrong.

ContentLicense: CC BY-SA 3.0

Title: Can encapsulation be implemented by proper types rather than accessors?

Body:
Interesting question came up while designing interfaces at work, now resolved, but I want to ask about the theory behind it.

Is it incorrect to say that properly typed data members of a class provide encapsulation? (e.g. a Boost Units type that has conversions well defined between other like units, not a typedef'd/boxed uint64_t)

```<code>struct Ruler
{
    Length length;
    Length tick_size;

    Ruler(Length length, Length tick_size);
    // Why not have helpers immediately related to the class, let's
    // stick in an alternative constructor
    Ruler(Length length, int number_ticks);

    // Accessors for # tick marks, because it needs transformed
    // to/from length and tick_size
    int GetNumberTicks(void);
    // This specific example breaks down with this function,
    // but I don't think it's an inherent issue with the design.
    // I need an overload so it will know which of the two member
    // variables to calculate... problem is both are Length
    void SetNumberTicks(int nticks);
}
</code>```

vs

```<code>struct Ruler
{
    Ruler(Length length, Length tick_size);
    Ruler(Length length, int number_ticks);

    // General accessors
    Length GetLength(void);
    void SetLength(Length length);

    Length GetTickSize(void);
    void SetTickSize(Length length);

    // Calculated accessors, see above
    int GetNumberTicks(void);
    void SetNumberTicks(int nticks);

private:
    Length length;
    Length tick_size;
}
</code>```

IMO the first encourages cleaner design by consumers and doesn't encourage pulling in slightly related, but probably attached to the wrong object member functions (eg CanMachineCreateRuler() ). I don't really have the words to describe this properly and I may be misunderstanding the additional utility that the accessors/private data combination provide.


问:
Regular syntax -- what does it mean?
I am reading "Less is exponentially more" and there is a list of advantages of Go, first of them, quote "regular syntax (don't need a symbol table to parse)".

What does it mean "regular syntax"? What properties define "language X does (not) have a regular syntax"?

答:
A look at the definition of Regular Language on Wikipedia could give you some pointers. Note that this goes into language theory and the Wikipedia article is not all that easy to read.

Basically, a regular language is a language that can be expressed by regular expressions.

I'm sure someone can manage to get into more details and still have the answer understandable by normal human beings, but that someone isn't me...

Title: Regular syntax -- what does it mean?


问:
Why was Scala not implemented with C or C++
Does anybody know why was Scala implemented in Java and .NET instead of C or C++? Most languages are implemented with Cor C++ [i.e Erlang, Python, PHP, Ruby, Perl]. What are the advantages for Scala implemented in Java and .NET other than giving access to Java and .NET libraries?

UPDATE

Wouldn't Scala gain more benefit if it were implemented in C because it can be tuned better rather than relying on JVM?

答:
First of all - what I guess you really wanted to ask is why Scala is not compiled language in it's strict manner. I will tell you I don't know. But I will tell you also that there is no reason to favor JVM over native code.

Why?
The reason is simple: any virtualization technology is memory hungry, produces unnecessary overhead and another layer of indirection. This is not a matter of their implementation - this is a matter of fact, of the logic that lies behind the core concept of virtualization. No matter what you do you will ALWAYS end up with inferior characteristics. Especially JVM is memory hungry. It's not anymore so slow, because it has it's own runtime compiler running behind the back, but still - it has to run the compiler process to be able to spot the most congested parts of code and turn them into binary code.

Said that - the only reason I think was there for making Scala JVM-based was probably the popularity of the language. I also guess that some laziness was behind this decission because it's easier to implement a language over the JVM than figure out how things should look like assembled to work cross platform - and even using existing C backends requires a lot more of work due to the fact that things are not as well standarized as with JVM.

That are the reason I can think of, but keep in mind that there may be other reasons - like licensing issuess and politics involved there (which are dirty things I won't ever like to get into).


答:
Languages like C++ require a symbol table to parse properly, because some constructs are syntactically ambiguous if you don't know whether a given token represents a type, a function or a variable.

The main concrete example that I'm aware of is that declaring functions and constructing values both use parentheses:

```<code>int foo(3); // creates an integer called foo with value 3
int bar(int); // creates a function called bar that takes an int and returns an int
</code>```

To parse this, you have to know that int is the name of a type and 3 is not. Because of user-defined types, in general you cannot know whether a given token is a type name unless you have a symbol table containing all types the parser has seen up to this point. Note that the infamous "Most Vexing Parse" is closely related to this particular ambiguity.

The author you've quoted is most likely claiming that the Go language has no ambiguities like this, and thus can be parsed correctly without a symbol table. If you look at the official Go language specification, you'll notice pretty much everything about the syntax comes with an EBNF definition. I haven't read through it thoroughly, but it seems likely that Go's syntax is an actual context-free grammar, not merely approximated by one, which is pretty nice compared to C++.

Title: Regular syntax -- what does it mean?

Body:
I am reading "Less is exponentially more" and there is a list of advantages of Go, first of them, quote "regular syntax (don't need a symbol table to parse)".

What does it mean "regular syntax"? What properties define "language X does (not) have a regular syntax"?

Body:
Languages like C++ require a symbol table to parse properly, because some constructs are syntactically ambiguous if you don't know whether a given token represents a type, a function or a variable.

The main concrete example that I'm aware of is that declaring functions and constructing values both use parentheses:

int foo(3); // creates an integer called foo with value 3
int bar(int); // creates a function called bar that takes an int and returns an int

To parse this, you have to know that int is the name of a type and 3 is not. Because of user-defined types, in general you cannot know whether a given token is a type name unless you have a symbol table containing all types the parser has seen up to this point. Note that the infamous "Most Vexing Parse" is closely related to this particular ambiguity.

The author you've quoted is most likely claiming that the Go language has no ambiguities like this, and thus can be parsed correctly without a symbol table. If you look at the official Go language specification, you'll notice pretty much everything about the syntax comes with an EBNF definition. I haven't read through it thoroughly, but it seems likely that Go's syntax is an actual context-free grammar, not merely approximated by one, which is pretty nice compared to C++.


问:
Shipping test code. Why wouldn't you?
I would like to ship test code alongside a product. Specifically, provide an option so that anyone with a copy of our program can hit a "self-test" button or pass --self-test on the command line and run through the complete suite of unit | integration tests.

I mostly want to do this to help debug problems discovered in the field, so when a bug report is incoming from an end user there's a chance of it being supported by "and also, these three tests failed on my machine". I'd like manual testers to be able to run the unit | integration tests as well.

However, the test of the team believes that test code is not production code and therefore shall not be shipped. I don't really get this argument, since most open source projects ship a test suite. It does seem to be unusual in closed software.

I would like supporting evidence or anecdotes for either side of the argument. I've taken my best guess at which stack exchange site would be most appropriate, but please let me know if this is out of place.

答:
I could understand this concern strongly in areas where you are covering every single inch of the hardware, like a multithreaded next-gen AAA game engine which uses every single CPU core, SIMD intrinsics, GPU, GPGPU, etc. while delivering a cross-platform product.

In those cases, your worst nightmare will often be those cases where your tests (unit and integration) will pass for the first 5,000 disparate machines/platforms tested, but fails for the 5,001th due to a driver bug for an obscure GPU model Just thinking about this gives me the shivers -- you cannot possibly test or foresee these in advance.

Especially if you write GPU shaders, you can end up playing a reverse lottery where half the code you write will invoke undefined behavior, since there are few portable standard guarantees enforced by all GPU models/drivers involved. While it's getting less and less like playing minesweeper these days, this should give people some idea: http://theorangeduck.com/page/writing-portable-opengl. Trying this in the late 90s and early 2000s was really horrible, and it was minesweeper all the way.

For these kinds of cases, you often need teams of 10,000+ testers with a really wide range of hardware and operating systems to really solidify the product and feel confident about it prior to a stable release. Not all companies can afford to have such a wide test base, and not all have the discipline to do it right (all widely-noticeable issues should be fixed prior to having so many testers in some internal pre-alpha/alpha stage or else the flood of redundant reports can throw developers into a patch-and-pray panic).

What I recommend in this case is what others suggested, focus on a distributed set of integration tests. You can bundle it up with the installer, requiring users to pass a basic diagnostics check with careful attention to providing details as to why the installation failed that they can pass to you, the developers.

Another thing (if you can convince the boss) is to have a wide range of hardware available to do contiguous integration. The more variety in hardware/OS combos, the merrier. You want even a variety of crap hardware that models the bare minimum hardware requirements for your CI servers: you never know.

But there's one more thing I'd suggest:

Logging

If you are dealing with anything like the scenario I described above, then often you cannot possibly test for these things which tend to be the most problematic (those worst possible gotchas which show up at the worst possible time and cannot possibly show up in even the most exhaustive test suite since it's an issue constrained to a very specific hardware/OS combo).

Yet most of those kinds of issues like obscure hardware incompatibilities or outright driver glitches or linking against the wrong dylib (I've never actually faced this concern) won't get you far past starting up the software. It's typically gonna crash and burn pretty soon, crudely speaking.

I recommend, for sanity sake, to kind of embrace the inevitable. You can't possibly do anything about these things you cannot possibly test comprehensively. Don't try to prevent the hurricane (impossible), but board up those windows.

Typically here, the best thing we can do is find out the problem as soon as possible, where it occurs as detailed as possible (to narrow our list of suspects), and have the issue fixed ASAP after it's reported.

In this case, logging can be a lifesaver. For these kinds of fields, you can create these spammy technical logs which no one would ever read through. Often relevant is just the very last line recorded in the log before the user faced a crash due to a driver glitch, e.g. You can write an external process or hook which monitors for crashes and then shows the last line of the log that users can copy and paste to you, e.g. in addition to a crash dump.

Since this often needs granular information and a lot of the most susceptible areas in code to these hardware/platform/driver issues is performance-critical, there's this awkward issue where the logging can be happening at such a frequent rate that it'll actually slow down the software.

A useful trick in this case is to rely on the assumption that something executed once will execute successfully the second time, third time, etc. This is not the most sound assumption, but it's often "good enough" (and infinitely better than nothing). With that, you can use a little bit of external state to keep track of when something has been logged already and skip subsequent attempts to log for those really granular cases where the code will be invoked repeatedly in a loop.

Anyway, I hope this helps. I've run into this kind of temptation in the past and have a bit of a paranoia surrounding GPU coding (GPGPU and shaders) as a result of some past experiences among myself and my team (sometimes just seeing other team members deal with these really late and post-release gave me the creeps, like some ATI glitch on a specific Radeon model which would crash on rendering antialiased lines, later reported and marked as a known problem with only a workaround solution available).

Logging was the thing that saved our butts there, letting us often see the issue on that 10,001th obscure prototype machine with an onboard GPU we never heard of, with the last line of code immediately letting us spot exactly where the failure was down to 2 or 3 lines of code as suspect, e.g. If it's inside an elaborate shader, we're kind of SOL since we can't do logging inside a GPU shader, but we can at least use logging to see which shader had the issue right away to start off the investigation.

Title: Shipping test code. Why wouldn't you?


问:
Do I update the copyright header when i modify the source?
Suppose I were to modify a said piece of code and put it back on github, would I have to update the license header.

This is the code(Licensed under the Apache License, Version 2.0): https://github.com/MasterAwesome/android_device_oneplus_onyx/commits/master/liblight/lights.c

The commit "Use liblights-caf" is from Google's repository. Now the next few commits I have made is to modify the source code for my device. Should I add my copyright notice in the header too?

答:
Updating the copyright header is a per-project type decision.

On larger projects, they copyright is typically updated only at major or minor release updates and not with every single commit to the codebase.  However, copyright on large projects is typically assigned to a single entity and there is controlled access to the code repository.  So in some cases, the answer is "No, don't update the copyright header."

On smaller projects, individual contribution is tracked through updates to the copyright header.  Based upon the patterns shown in the project you linked, it appears that the standard for that project is to update with each commit.  So yes, you should update the copyright header for that particular project.

Ultimately, the answer is to check on the project and see what others are doing.


问:
Activity Feed Object to Notify Users
We're developing a transactional application in .NET (ASP.NET MVC, C#, Workflow Foundation, EntityFramework), and want to implement a system whereby users are notified of work that needs to be done based on events in the system.  For instance, if an external interface call results in the cost for Widget A to be updated, then the user may want to go update the retail price for Widget A, or at least review it, so they need to be notified of the cost update.

Microsoft Dynamics CRM has the concept of Activity Feeds and the objects to support it.  It seems to be the right sort of thing for what I need, though it also seems like a lot of infrastructure that I might not need.  On the other hand, rolling my own seems like a good way to miss something important.

Before I go running down the rabbit hole of implementing one extreme or the other, I thought I'd ask here for a suggestion of something better (defined as less footprint than Dynamics CRM, yet pre-defined so I don't have to build my own).  If I roll my own, I'm considering something like the following:

```<code>public class UserNotification
{
    // Notifications will go to Roles (groups of users)
    public Role RoleToNotify { get; set; }

    // A notification will be about an object that needs to be worked on
    public Type TypeOfThing { get; set; }
    public long IdOfThing { get; set; }

    // Time tracking
    public DateTime TimeOfNotification { get; set; }
    public DateTime TimeOfUserAction { get; set; }
}
</code>```

Is there an alternative approach I should be considering?

答:
It sounds like what you've described is a text-book example of when you should use the publish subscribe pattern, which is also known as the pub sub pattern.

Pub Sub is used when you have a Sender (e.g. Widget price update) and a variable number of Subscribers (e.g. parties interested in the price change), and what you described is a classic case for it.

As far as using the MS Dynamics CRM or rolling your own, I would certainly vote against rolling your own.  Event queues aren't super complicated, but there are a large number of 3rd party providers that have already done that work for you and there's little for you to gain by rolling your own.  Looking at the Wikipedia page for Message Broker software will give you a starting point, and depending upon your environment's requirements you'll easily be able to find something that meets your needs.

Title: Activity Feed Object to Notify Users


问:
Custom heap allocators
Most programs can be quite casual about heap allocation, even to the extent that functional programming languages prefer to allocate new objects than modify old ones, and let the garbage collector worry about freeing things.

In embedded programming, the silent sector, however, there are many applications where you can't use heap allocation at all, due to memory and hard real-time constraints; the number of objects of each type that will be handled is part of the specification, and everything is statically allocated.

Games programming (at least with those games that are ambitious about pushing the hardware) sometimes falls in between: you can use dynamic allocation, but there are enough memory and soft real-time constraints that you can't treat the allocator as a black box, let alone use garbage collection, so you have to use custom allocators. This is one of the reasons C++ is still widely used in the games industry; it lets you do things like http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

What other domains are in that in-between territory? Where, apart from games, are custom allocators heavily used?

答:
Video processing, VFX, operating systems, etc.  Often people overuse them though. The data structure and allocator need not be separated to achieve efficient allocation.

For example, it's introducing a lot of extra complexity to split efficient tree node allocation in an octree away from the octree itself and rely on an external allocator. It's not necessarily a violation of SRP to fuse these two concerns together and make it the responsibility of the octree to allocate many nodes at once contiguously, as doing that does not increase the number of reasons to change. It may, practically speaking, decrease it.

In C++, for example, one of the retarded side effects of having standard containers rely on an external allocator has made linked structures like std::map and std::list considered almost useless by the C++ community, since they're benchmarking them against std::allocator while these data structures allocate one node at a time. Of course your linked structures are going to perform poorly in that case, but things would have turned out so much differently if efficient allocation of nodes for linked structures was considered a data structure's responsibility rather than an allocator's. They might still use a custom allocation for other reasons like memory tracking/profiling, but to rely on the allocator to make linked structures efficient while trying to allocate nodes one-at-a-time makes all of them, by default, extremely inefficient, which would be okay if it came with a well-known caveat that linked structures now need a custom allocator, like free list, to be reasonably efficient and avoid triggering cache misses left and right. Far more practically applicable might have been something like std::list<T, BlockSize, Alloc>, where BlockSize indicates the number of contiguous nodes to allocate at once for the free list (specifying 1 would effectively lead to std::list as it is now).

But there is no such caveat, which then leads to a whole community of blockheads echoing a cult mantra that linked lists are useless, e.g.

Title: Custom heap allocators


问:
Managing widgets in a simple GUI framework
So, I'm still working on my small GUI "library". (C++ with boost)
The goal is to provide a simple solution for small SPI displays, using a Raspberry or some embedded board.

Thus, I ended up having a Widget class from which concrete widgets are derived.
Examples would be a textbox or an image frame.
Widgets can contain other widgets to allow groups.
This is achieved via aggregation using a STL container.
In the end, the complete GUI dataset can be seen as some kind of tree, with some nodes having child nodes.

Each widget shall have a draw-method which looks like

```<code>    void drawMe(brush *myBrush);
</code>```

A brush provides primitive drawing methods like "setPixel" or "drawRectangle"
This allows the widget to draw itself, using the methods provided by the brush.
A widget first draws itself, then it invokes the drawMe-method of each child widget, if any.

Now lets talk about my problem.
Each widget has its coordinates, relative to the parent.
This is not enough, the brush needs the absolute coordinate of the widget, because a brush does not know anything about children or parents. A brush just provides methods like setPixel(int x, int y) and draws into a pixel buffer.

But I somehow have a bad feeling letting a widgets know its absolute coordinates. This feels wrong.
On the other hand, at the moment a child does not know it is owned by a parent, thus, there's no way a widget can compute its absolute coordinates.

I can implement workaround in the brush, so that the brush supports multiple layers instead of just one canvas (the pixel buffer). A parent then has to set up the layers for its child.
Sounds like a dirty hack.

Also, is it a good idea to et the parent know its child coordinates?

You see, I'm somewhere lost with this issues.
There are GUI frameworks out there, like QT and stuff.
So, my problem should be known and solved already.
Do you have any suggestions?
How would you implement the drawing process?

The whole project is about learning new stuff, mainly OOP paradigms.
I like to hear your opinion on that.

答:
But I somehow have a bad feeling letting a widgets know its absolute
  coordinates. This feels wrong.

Good instincts. The data would be redundant and trivially computed from the combination of a parent widget and child widget's local coordinates. Less state often means less room for error (plus reduced memory use per widget).


问:
Memory management for fast message passing between threads in C++
Suppose there are two threads, which communicate by asynchronously sending data messages to each other. Each thread has some kind of message queue.

My question is very low level: What can be expected to be the most efficient way to manage the memory? I can think of several solutions:

Sender creates the object via new. Receiver calls delete.

Memory pooling (to transfer the memory back to the sender)

Garbage collection (e.g., Boehm GC)

(if the objects are small enough) copy by value to avoid heap allocation completely

1) is the most obvious solution, so I'll use it for a prototype. Chances are that it is already good enough. But independent of my specific problem, I wonder which technique is most promising if you are optimizing for performance.

I would expect pooling to be theoretically the best, especially because you can use extra knowledge about the flow of information between the threads. However, I fear that it is also the most difficult to get right. Lots of tuning... :-(

Garbage collection should be quite easy to add afterwards (after solution 1), and I would expect it to perform very well. So, I guess that it is the most practical solution if 1) turns out to be too inefficient.

If the objects are small and simple, copy by value might be the fastest. However, I fear that it forces unnecessary limitations on the implementation of the supported messages, so I want to avoid it.

答:
The biggest performance hit when communicating an object from one thread to another is the overhead of grabbing a lock. This is on the order of several microseconds, which is significantly more than the average time a pair of new/delete takes (on the order of a hundred nanoseconds). Sane new implementations try to avoid locking at nearly all costs to avoid their performance hit.

That said, you want to ensure that you don't need to grab locks when communicating the objects from one thread to another. I know two general methods to achieve this. Both work only unidirectionally between one sender and one receiver:

Use a ring buffer. Both processes control one pointer into this buffer, one is the read pointer, the other is the write pointer.

The sender first checks if there is room to add an element by comparing the pointers, then adds the element, then increments the write pointer.

The receiver checks if there is an element to read by comparing the pointers, then reads the element, then increments the read pointer.

The pointers need to be atomical as they are shared between the threads. However, each pointer is only modified by one thread, the other needs only read access to the pointer. The elements in the buffer may be pointers themselves, which allows you to easily size your ring buffer to a size that won't make the sender block.

Use a linked list that always contains at least one element. The receiver has a pointer to the first element, the sender has a pointer to the last element. These pointer are not shared.

The sender creates a new node for the linked list, setting its next pointer to nullptr. Then it updates the next pointer of the last element to point to the new element. Finally, it stores the new element in its own pointer.

The receiver watches the next pointer of the first element to see if there is new data available. If so, it deletes the old first element, advances its own pointer to point to the current element and starts processing it.

In this setup, the next pointers need to be atomic, and the sender must be sure not to dereference the second last element after it has set its next pointer. The advantage is, of course, that the sender never has to block.

Both approaches are much faster than any lock-based approach, but they require careful implementation to get right. And, of course, they require native hardware atomicity of pointer writes/loads; if your atomic<> implementation uses a lock internally, you are pretty much doomed.

Likewise, if you have several readers and/or writers, you are pretty much doomed: You may try to come up with a lock-less scheme, but it will be tricky to implement at best. These situations are much easier to handle with a lock. However, once you grab a lock, you can stop worrying about new/delete performance.


问:
Does object-orientation really affect algorithm performance?
Object orientation has helped me a lot in implementing many algorithms. However, object-oriented languages sometimes guide you in "straightforward" approach and I doubt if this approach is always a good thing.

OO is really helpful in coding algorithms fast and easily. But could this OOP be a disadvantage for software based on performance i.e. how fast does the programm executes?

For example, storing graph nodes in a data structure seems "straightforward" in the first place, but if Node objects contain many attributes and methods, could this lead to a slow algorithm?

In other words, could many references between many different objects, or using many methods from many classes, result in a "heavy" implementation?

答:
But could this OOP be a disadvantage for software based on performance
  i.e. how fast does the programm executes?

Often Yes!!! BUT...

In other words, could many references between many different objects,
  or using many methods from many classes, result in a "heavy"
  implementation?

Not necessarily. This depends on the language/compiler. For example, an optimizing C++ compiler, provided that you don't use virtual functions, will often squash down your object overhead to zero. You can do things like write a wrapper over an int there or a scoped smart pointer over a plain old pointer which performs just as fast as using these plain old data types directly.

In other languages like Java, there is a bit of an overhead to an object (often quite small in many cases, but astronomical in some rare cases with really teeny objects). For example, Integer there is considerably less efficient than int (takes 16 bytes as opposed to 4 on 64-bit). Yet this isn't just blatant waste or anything of that sort. In exchange, Java offers things like reflection on every single user-defined type uniformly, as well as the ability to override any function not marked as final.

Yet let's take the best-case scenario: the optimizing C++ compiler which can optimize object interfaces down to zero overhead. Even then, OOP will often degrade performance and prevent it from reaching the peak. That might sound like a complete paradox: how could it be? The problem lies in:

Interface Design and Encapsulation

The problem is that even when a compiler can squash an object's structure down to zero overhead (which is at least very often true for optimizing C++ compilers), the encapsulation and interface design (and dependencies accumulated) of fine-grained objects will often prevent the most optimal data representations for objects that are intended to be aggregated by the masses (which is often the case for performance-critical software).

Take this example:

class Particle
{
public:
    ...

private:
    double birth;                // 8 bytes
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
    /*padding*/                  // 4 bytes of padding
};
Particle particles[1000000];     // 1mil particles (~24 megs)
```

<p>Let's say our memory access pattern is to simply loop through these particles sequentially and move them around each frame repeatedly, bouncing them off the corners of the screen and then rendering the result.</p>

<p>Already we can see a glaring 4 byte padding overhead required to align the <code>birth</code> member properly when particles are aggregated contiguously. Already ~16.7% of the memory is wasted with dead space used for alignment.</p>

<p>This might seem moot because we have gigabytes of DRAM these days. Yet even the most beastly machines we have today often only have a mere 8 megabytes when it comes to the <em>slowest and biggest</em> region of the CPU cache (L3). The less we can fit in there, the more we pay for it in terms of repeated DRAM access, and the slower things get. Suddenly, wasting 16.7% of memory no longer seems like a trivial deal.</p>

<p>We can easily eliminate this overhead without any impact on field alignment:</p>

<pre class="lang-cpp prettyprint-override"><code>class Particle
{
public:
    ...

private:
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
};
Particle particles[1000000];     // 1mil particles (~12 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)
</code>```

Now we've reduced the memory from 24 megs to 20 megs. With a sequential access pattern, the machine will now consume this data quite a bit faster.

But let's look at this birth field a bit more closely. Let's say it records the starting time when a particle is born (created). Imagine the field is only accessed when a particle is first created, and every 10 seconds to see if a particle should die and become reborn in a random location on the screen. In that case, birth is a cold field. It's not accessed in our performance-critical loops.

As a result, the actual performance-critical data is not 20 megabytes but actually a 12-megabyte contiguous block. The actual hot memory we're accessing frequently has shrunk to half its size! Expect significant speed-ups over our original, 24-megabyte solution (doesn't need to be measured -- already done this kind of stuff a thousand times, but feel free if in doubt).

Yet notice what we did here. We completely broke the encapsulation of this particle object. Its state is now split between a Particle type's private fields and a separate, parallel array. And that's where granular object-oriented design gets in the way.

We can't express the optimal data representation when confined to the interface design of a single, very granular object like a single particle, a single pixel, even a single 4-component vector, possibly even a single "creature" object in a game, etc. A cheetah's speed will be wasted if it's standing on a teeny island that's 2 sq. meters, and that's what very granular object-oriented design often does in terms of performance. It confines the data representation to a sub-optimal nature.

To take this further, let's say that since we're just moving particles around, we can actually access their x/y/z fields in three separate loops. In that case, we can benefit from SoA style SIMD intrinsics with AVX registers that can vectorize 8 SPFP operations in parallel. But to do this, we must now use this representation:

float particle_x[1000000];       // 1mil particle X positions (~4 megs)
float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)
```

<p>Now we're flying with the particle simulation, but look what happened to our particle design. It has been completely demolished, and we're now looking at 4 parallel arrays and no object to aggregate them whatsoever. Our object-oriented <code>Particle</code> design has gone sayonara.</p>

<p>This happened to me many times working in performance-critical fields where users demand speed with only correctness being the one thing they demand more. These little teeny object-oriented designs had to be demolished, and the cascading breakages often required that we used a slow deprecation strategy towards the faster design.</p>

<h2>Solution</h2>

<p>The above scenario only presents a problem with <em>granular</em> object-oriented designs. In those cases, we often end up having to demolish the structure in order to express more efficient representations as a result of SoA reps, hot/cold field splitting, padding reduction for sequential access patterns (padding is sometimes helpful for performance with random-access patterns in AoS cases, but almost always a hindrance for sequential access patterns), etc.</p>

<p>Yet we can take that final representation we settled on and still model an object-oriented interface:</p>

<pre class="lang-cpp prettyprint-override"><code>// Represents a collection of particles.
class ParticleSystem
{
public:
    ...

private:
    double particle_birth[1000000];  // 1mil particle births (~8 bytes)
    float particle_x[1000000];       // 1mil particle X positions (~4 megs)
    float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
    float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
};
</code>```

Now we're good. We can get all the object-oriented goodies we like. The cheetah has a whole country to run across as fast as it can. Our interface designs no longer trap us into a bottleneck corner.

ParticleSystem can potentially even be abstract and use virtual functions. It's moot now, we're paying for the overhead at the collection of particles level instead of at a per-particle level. The overhead is 1/1,000,000th of what it would be otherwise if we were modeling objects at the individual particle level.

So that's the solution in true performance-critical areas that handle a heavy load, and for all kinds of programming languages (this technique benefits C, C++, Python, Java, JavaScript, Lua, Swift, etc). And it can't easily be labeled as "premature optimization", since this relates to interface design and architecture. We can't write a codebase modeling a single particle as an object with a boatload of client dependencies to a Particle's public interface and then change our minds later. I've done that a lot when being called to optimize legacy codebases, and that can end up taking months of rewriting tens of thousands of lines of code carefully to use the bulkier design. This ideally affects how we design things upfront provided that we can anticipate a heavy load.

I keep echoing this answer in some form or another in many performance questions, and especially ones that relate to object-oriented design. Object-oriented design can still be compatible with the highest-demand performance needs, but we have to change the way we think about it a little bit. We have to give that cheetah some room to run as fast as it can, and that's often impossible if we design teeny little objects that barely store any state.

Body:
But could this OOP be a disadvantage for software based on performance
  i.e. how fast does the programm executes?

Often Yes!!! BUT...

In other words, could many references between many different objects,
  or using many methods from many classes, result in a "heavy"
  implementation?

Not necessarily. This depends on the language/compiler. For example, an optimizing C++ compiler, provided that you don't use virtual functions, will often squash down your object overhead to zero. You can do things like write a wrapper over an int there or a scoped smart pointer over a plain old pointer which performs just as fast as using these plain old data types directly.

In other languages like Java, there is a bit of an overhead to an object (often quite small in many cases, but astronomical in some rare cases with really teeny objects). For example, Integer there is considerably less efficient than int (takes 16 bytes as opposed to 4 on 64-bit). Yet this isn't just blatant waste or anything of that sort. In exchange, Java offers things like reflection on every single user-defined type uniformly, as well as the ability to override any function not marked as final.

Yet let's take the best-case scenario: the optimizing C++ compiler which can optimize object interfaces down to zero overhead. Even then, OOP will often degrade performance and prevent it from reaching the peak. That might sound like a complete paradox: how could it be? The problem lies in:

Interface Design and Encapsulation

The problem is that even when a compiler can squash an object's structure down to zero overhead (which is at least very often true for optimizing C++ compilers), the encapsulation and interface design (and dependencies accumulated) of fine-grained objects will often prevent the most optimal data representations for objects that are intended to be aggregated by the masses (which is often the case for performance-critical software).

Take this example:

class Particle
{
public:
    ...

private:
    double birth;                // 8 bytes
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
    /*padding*/                  // 4 bytes of padding
};
Particle particles[1000000];     // 1mil particles (~24 megs)

Let's say our memory access pattern is to simply loop through these particles sequentially and move them around each frame repeatedly, bouncing them off the corners of the screen and then rendering the result.

Already we can see a glaring 4 byte padding overhead required to align the birth member properly when particles are aggregated contiguously. Already ~16.7% of the memory is wasted with dead space used for alignment.

This might seem moot because we have gigabytes of DRAM these days. Yet even the most beastly machines we have today often only have a mere 8 megabytes when it comes to the slowest and biggest region of the CPU cache (L3). The less we can fit in there, the more we pay for it in terms of repeated DRAM access, and the slower things get. Suddenly, wasting 16.7% of memory no longer seems like a trivial deal.

We can easily eliminate this overhead without any impact on field alignment:

class Particle
{
public:
    ...

private:
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
};
Particle particles[1000000];     // 1mil particles (~12 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

Now we've reduced the memory from 24 megs to 20 megs. With a sequential access pattern, the machine will now consume this data quite a bit faster.

But let's look at this birth field a bit more closely. Let's say it records the starting time when a particle is born (created). Imagine the field is only accessed when a particle is first created, and every 10 seconds to see if a particle should die and become reborn in a random location on the screen. In that case, birth is a cold field. It's not accessed in our performance-critical loops.

As a result, the actual performance-critical data is not 20 megabytes but actually a 12-megabyte contiguous block. The actual hot memory we're accessing frequently has shrunk to half its size! Expect significant speed-ups over our original, 24-megabyte solution (doesn't need to be measured -- already done this kind of stuff a thousand times, but feel free if in doubt).

Yet notice what we did here. We completely broke the encapsulation of this particle object. Its state is now split between a Particle type's private fields and a separate, parallel array. And that's where granular object-oriented design gets in the way.

We can't express the optimal data representation when confined to the interface design of a single, very granular object like a single particle, a single pixel, even a single 4-component vector, possibly even a single "creature" object in a game, etc. A cheetah's speed will be wasted if it's standing on a teeny island that's 2 sq. meters, and that's what very granular object-oriented design often does in terms of performance. It confines the data representation to a sub-optimal nature.

To take this further, let's say that since we're just moving particles around, we can actually access their x/y/z fields in three separate loops. In that case, we can benefit from SoA style SIMD intrinsics with AVX registers that can vectorize 8 SPFP operations in parallel. But to do this, we must now use this representation:

float particle_x[1000000];       // 1mil particle X positions (~4 megs)
float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

Now we're flying with the particle simulation, but look what happened to our particle design. It has been completely demolished, and we're now looking at 4 parallel arrays and no object to aggregate them whatsoever. Our object-oriented Particle design has gone sayonara.

This happened to me many times working in performance-critical fields where users demand speed with only correctness being the one thing they demand more. These little teeny object-oriented designs had to be demolished, and the cascading breakages often required that we used a slow deprecation strategy towards the faster design.

Solution

The above scenario only presents a problem with granular object-oriented designs. In those cases, we often end up having to demolish the structure in order to express more efficient representations as a result of SoA reps, hot/cold field splitting, padding reduction for sequential access patterns (padding is sometimes helpful for performance with random-access patterns in AoS cases, but almost always a hindrance for sequential access patterns), etc.

Yet we can take that final representation we settled on and still model an object-oriented interface:

// Represents a collection of particles.
class ParticleSystem
{
public:
    ...

private:
    double particle_birth[1000000];  // 1mil particle births (~8 bytes)
    float particle_x[1000000];       // 1mil particle X positions (~4 megs)
    float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
    float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
};

Now we're good. We can get all the object-oriented goodies we like. The cheetah has a whole country to run across as fast as it can. Our interface designs no longer trap us into a bottleneck corner.

ParticleSystem can potentially even be abstract and use virtual functions. It's moot now, we're paying for the overhead at the collection of particles level instead of at a per-particle level. The overhead is 1/1,000,000th of what it would be otherwise if we were modeling objects at the individual particle level.

So that's the solution in true performance-critical areas that handle a heavy load, and for all kinds of programming languages (this technique benefits C, C++, Python, Java, JavaScript, Lua, Swift, etc). And it can't easily be labeled as "premature optimization", since this relates to interface design and architecture. We can't write a codebase modeling a single particle as an object with a boatload of client dependencies to a Particle's public interface and then change our minds later. I've done that a lot when being called to optimize legacy codebases, and that can end up taking months of rewriting tens of thousands of lines of code carefully to use the bulkier design. This ideally affects how we design things upfront provided that we can anticipate a heavy load.

I keep echoing this answer in some form or another in many performance questions, and especially ones that relate to object-oriented design. Object-oriented design can still be compatible with the highest-demand performance needs, but we have to change the way we think about it a little bit. We have to give that cheetah some room to run as fast as it can, and that's often impossible if we design teeny little objects that barely store any state.


问:
Is Dependency Inversion a valid alternative to the pImpl idiom?
If I want to present to the user of my code an interface, that is unlikely to change, I can write only the public part of the classes in public headers and have a single private pointer to another object, that holds the private declarations. I believe this is known as The pImpl idiom.

Now imagine another approach. The public part of the class is placed into an IClass or ClassBase or whatever class, placed in the public headers. Then, in a private header (== not exposed to the user), this base class is inherited and it's methods implemented.

To me it seems that the second approach achieves the same goals as the first one. But are there any drawbacks? When to prefer which?

答:
Let's consider as close to an apples to apples comparison as we can, meaning you are using this base class only to derive it one time in a class that's not publicly visible and discounting the extensibility of this solution. The sole purpose of using an abstraction here is to hide one concrete implementation, nothing more (as with the pimpl case).

So we have something like this (abstract interface):

// In some header file:
class IFoo
{
public:
    virtual ~IFoo() {}
    virtual void do_something() = 0;
};
std::unique_ptr<IFoo> create_foo();

// Inside source file (hidden from the outside world):
class Foo: public IFoo
{
    ...
};

std::unique_ptr<IFoo> create_foo()
{
    return std::unique_ptr<IFoo>(new Foo);
}
```

<p>vs. Pimpl:</p>

<pre class="lang-cpp prettyprint-override"><code>// In some header file:
class Foo
{
public:
    Foo();
    Foo(const Foo& other);
    Foo& operator=(const Foo& other);
    ~Foo();

    void do_something();

private:
    struct Impl;
    std::unique_ptr<Impl> priv;
};

// Inside source file (hidden from the outside world):
struct Foo::Impl
{
    ...
};

Foo::Foo(): priv(new Impl)
{
}
...
</code>```

In Common

What these both have in common is that they serve the same fundamental premise: they hide the implementation details from the outside world, they reduce compile-time dependencies.

The abstract interface arguably does this ever so slightly more, not even exposing a Pimpl at all, though typically this is getting into really moot pedantic territory. It might be a favorable aesthetic to some, making only the public interface/documentation visible in the header (if header aesthetics are valued).

Both suffer from the need for dynamic allocation, an extra pointer, and disjointed memory representation from pointer to pointee as well as a potential loss of spatial locality from one pointee to the next. The memory inefficiency can be mitigated considerably for both cases by a fixed allocator to pool chunks of memory from a contiguous pool for pointees to use.

Different

Some things different between these two:

The abstract interface version requires a dynamic (aka virtual) dispatch overhead per member function call. This may be moot for deeper pipelines where a reasonable amount of work is done in a member function. It may turn into a minor hotspot for teeny member functions called in huge numbers (ex: millions and millions of times) in tight loops for some simple accessor function (both due to shallow pipeline and the optimization barrier which prevents inlining). I generally wouldn't worry about this too much pre-measurements, since you always have the option of turning IFoo from a pure interface into an abstract base class and inlining some critical functions if absolutely necessary without redesigning the whole thing.

The abstract version requires a vptr overhead per instance and a vtable to be generated per class.

The pimpl version can provide value/copy/move semantics directly without the need for yet another wrapper (the abstract version would require it, along with either virtual methods like clone or external functions like clone that are implemented inside the source file where Foo is visible).

The abstract version is arguably a little more straight-forward to implement (and arguably also read), as it lets you avoid dealing with managing this separate pimpl storing the implementation details and just lets you define a new class and override some virtual functions all in one go.

The abstract version is a little more flexible (ex: we can have two or more separate concrete implementations of IFoo living in the same codebase). This is getting away from striving for the apples to apples comparison, however, and noting more that this is apples to oranges.

The abstract version has a more fragile ABI, as adding any new virtual function anywhere will break the vtable ABI. This is only important in contexts like software development kits used by plugin developers where the binaries aren't all being built/distributed together.

I think that covers the main differences. Note that object slicing isn't a concern here provided that IFoo cannot be instantiated on its own.

Body:
Let's consider as close to an apples to apples comparison as we can, meaning you are using this base class only to derive it one time in a class that's not publicly visible and discounting the extensibility of this solution. The sole purpose of using an abstraction here is to hide one concrete implementation, nothing more (as with the pimpl case).

So we have something like this (abstract interface):

// In some header file:
class IFoo
{
public:
    virtual ~IFoo() {}
    virtual void do_something() = 0;
};
std::unique_ptr<IFoo> create_foo();

// Inside source file (hidden from the outside world):
class Foo: public IFoo
{
    ...
};

std::unique_ptr<IFoo> create_foo()
{
    return std::unique_ptr<IFoo>(new Foo);
}

vs. Pimpl:

// In some header file:
class Foo
{
public:
    Foo();
    Foo(const Foo& other);
    Foo& operator=(const Foo& other);
    ~Foo();

    void do_something();

private:
    struct Impl;
    std::unique_ptr<Impl> priv;
};

// Inside source file (hidden from the outside world):
struct Foo::Impl
{
    ...
};

Foo::Foo(): priv(new Impl)
{
}
...

In Common

What these both have in common is that they serve the same fundamental premise: they hide the implementation details from the outside world, they reduce compile-time dependencies.

The abstract interface arguably does this ever so slightly more, not even exposing a Pimpl at all, though typically this is getting into really moot pedantic territory. It might be a favorable aesthetic to some, making only the public interface/documentation visible in the header (if header aesthetics are valued).

Both suffer from the need for dynamic allocation, an extra pointer, and disjointed memory representation from pointer to pointee as well as a potential loss of spatial locality from one pointee to the next. The memory inefficiency can be mitigated considerably for both cases by a fixed allocator to pool chunks of memory from a contiguous pool for pointees to use.

Different

Some things different between these two:

The abstract interface version requires a dynamic (aka virtual) dispatch overhead per member function call. This may be moot for deeper pipelines where a reasonable amount of work is done in a member function. It may turn into a minor hotspot for teeny member functions called in huge numbers (ex: millions and millions of times) in tight loops for some simple accessor function (both due to shallow pipeline and the optimization barrier which prevents inlining). I generally wouldn't worry about this too much pre-measurements, since you always have the option of turning IFoo from a pure interface into an abstract base class and inlining some critical functions if absolutely necessary without redesigning the whole thing.

The abstract version requires a vptr overhead per instance and a vtable to be generated per class.

The pimpl version can provide value/copy/move semantics directly without the need for yet another wrapper (the abstract version would require it, along with either virtual methods like clone or external functions like clone that are implemented inside the source file where Foo is visible).

The abstract version is arguably a little more straight-forward to implement (and arguably also read), as it lets you avoid dealing with managing this separate pimpl storing the implementation details and just lets you define a new class and override some virtual functions all in one go.

The abstract version is a little more flexible (ex: we can have two or more separate concrete implementations of IFoo living in the same codebase). This is getting away from striving for the apples to apples comparison, however, and noting more that this is apples to oranges.

The abstract version has a more fragile ABI, as adding any new virtual function anywhere will break the vtable ABI. This is only important in contexts like software development kits used by plugin developers where the binaries aren't all being built/distributed together.

I think that covers the main differences. Note that object slicing isn't a concern here provided that IFoo cannot be instantiated on its own.


问:
Is Java much harder to "tweak" for performance compared with C/C++?
Does the "magic" of the JVM hinder the influence a programmer has over micro-optimisations in Java? I recently read in C++ sometimes the ordering of the data members can provide optimizations (granted, in the microsecond environment) and I presumed a programmer's hands are tied when it comes to squeezing performance from Java?

I appreciate a decent algorithm provides greater speed-gains, but once you have the correct algorithm is Java harder to tweak due to the JVM control?

If not, could people give examples of what tricks you can use in Java (besides simple compiler flags).

答:
[...] (granted, in the microsecond environment) [...]

Micro-seconds add up if we're looping over millions to billions of things. A personal vtune/micro-optimization session from C++ (no algorithmic improvements):

```<code>T-Rex (12.3 million facets):
Initial Time: 32.2372797 seconds
Multithreading: 7.4896073 seconds
4.9201039 seconds
4.6946372 seconds
3.261677 seconds
2.6988536 seconds
SIMD: 1.7831 seconds
4-valence patch optimization: 1.25007 seconds
0.978046 seconds
0.970057 seconds
0.911041 seconds
</code>```

Everything besides "multithreading", "SIMD" (handwritten to beat the compiler), and the 4-valence patch optimization were micro-level memory optimizations. Also the original code starting from the initial times of 32 seconds was already optimized quite a bit (theoretically-optimal algorithmic complexity) and this is a recent session. The original version long before this recent session took over 5 minutes to process.

Optimizing memory efficiency can help often by anywhere from several times to orders of magnitudes in a single-threaded context, and more in multithreaded contexts (the benefits of an efficient memory rep often multiply with multiple threads in the mix).

On the Importance of Micro-Optimization

I get a little agitated by this idea that micro-optimizations are a waste of time. I agree that it's good general advice, but not everyone does it incorrectly based on hunches and superstitions rather than measurements. Done correctly, it doesn't necessarily yield a micro impact. If we take Intel's own Embree (raytracing kernel) and test only the simple scalar BVH they've written (not ray packet which is exponentially harder to beat), and then try to beat the performance of that data structure, it can be a most humbling experience even for a veteran used to profiling and tuning code for decades. And it's all because of micro-optimizations applied. Their solution can process over a hundred million rays per second when I've seen industrial professionals working in raytracing who can't even get more than 3 million rays per second on the same hardware (same bounding volume hierarchy, same logarithmic search).

There's no way to take a straightforward implementation of a BVH with only an algorithmic focus and get over a hundred million primary ray intersections per second out of it against any optimizing compiler (even Intel's own ICC). A straightforward one often doesn't even get a million rays per second. It takes professional-quality solutions to often even get a few million rays per second. It takes Intel-level micro-optimization to get over a hundred million rays per second.

Algorithms

I think micro-optimization isn't important as long as performance isn't important at the level of minutes to seconds, e.g., or hours to minutes. If we take a horrific algorithm like bubble sort and use it over a mass input as an example, and then compare it to even a basic implementation of merge sort, the former might take months to process, the latter maybe 12 minutes, as a result of quadratic vs linearithmic complexity.

The difference between months and minutes is probably going to make most people, even those not working in performance-critical fields, consider the execution time to be unacceptable if it requires users waiting for months to get a result.

Meanwhile, if we compare the non-micro-optimized, straightforward merge sort to quicksort (which is not at all algorithmically superior to merge sort, and only offers micro-level improvements for locality of reference), the micro-optimized quicksort might finish in 15 seconds as opposed to 12 minutes. Making users wait 12 minutes might be perfectly acceptable (coffee break kind of time).

I think this difference is probably negligible to most people between, say, 12 minutes and 15 seconds, and that's why micro-optimization is often considered useless since it's often only like the difference between minutes and seconds, and not minutes and months. The other reason I think it's considered useless is that it's often applied to areas that don't matter: some little area which isn't even loopy and critical which yields some questionable 1% difference (which may very well just be noise). But for people who care about these types of time differences and are willing to measure and do it right, I think it's worth paying attention to at least the basic concepts of the memory hierarchy (specifically the upper levels relating to page faults and cache misses).

Java Leaves Plenty of Room for Good Micro-Optimizations

Phew, sorry -- with that sort of rant aside:

Does the "magic" of the JVM hinder the influence a programmer has over
  micro-optimisations in Java?

A little bit but not as much as people might think if you do it right. For example, if you are doing image processing, in native code with handwritten SIMD, multithreading, and memory optimizations (access patterns and possibly even representation depending on image processing algorithm), it's easy to crunch hundreds of millions of pixels per second for 32-bit RGBA pixels (8-bit color channels) and sometimes even billions per second.

It's impossible to get anywhere close in Java if you say, made a Pixel object (this alone would inflate the size of a pixel from 4 bytes to 16 on 64-bit).

But you might be able to get a whole lot closer if you avoided the Pixel object, used an array of bytes, and modeled an Image object. Java's still pretty competent there if you start using arrays of plain old data. I've tried these kinds of things before in Java and was quite impressed provided that you don't create a bunch of little teeny objects everywhere that are 4 times bigger than normal (ex: use int instead of Integer) and start modeling bulk interfaces like an Image interface, not Pixel interface. I'd even venture to say that Java can rival C++ performance if you are looping over plain old data and not objects (huge arrays of float, e.g., not Float).

Perhaps even more important than the memory sizes is that an array of int guarantees a contiguous representation. An array of Integer does not. Contiguity is often essential for locality of reference since it means multiple elements (ex: 16 ints) can all fit into a single cache line and potentially be accessed together prior to eviction with efficient memory access patterns. Meanwhile a single Integer might be stranded somewhere in memory with surrounding memory being irrelevant, only to have that region of memory loaded into a cache line only to use a single integer prior to eviction as opposed to 16 integers. Even if we got marvelously lucky and surrounding Integers were all right next to each other in memory, we can only fit 4 into a cache line that can be accessed prior to eviction as a result of Integer being 4 times larger, and that's in the best-case scenario.

And there's plenty of micro-optimizations to be had there since we're unified under the same memory architecture/hierarchy. Memory access patterns matter no matter what language you use, concepts like loop tiling/blocking might be generally applied far more often in C or C++, but they benefit Java just as much.

I recently read in C++ sometimes the ordering of the data members can
  provide optimizations [...]

The order of data members generally don't matter in Java, but that's mostly a good thing. In C and C++, preserving the order of data members is often important for ABI reasons so compilers don't mess with that. Human developers working there have to be careful to do things like arrange their data members in descending order (largest to smallest) to avoid wasting memory on padding. With Java, apparently the JIT can reorder the members for you on the fly to ensure proper alignment while minimizing padding, so provided that's the case, it automates something that average C and C++ programmers can often do poorly and end up wasting memory that way (which isn't just wasting memory, but often wasting speed by increasing the stride between AoS structures needlessly and causing more cache misses). It's a very robotic thing to rearrange fields to minimize padding, so ideally humans don't deal with that. The only time where field arrangement might matter in a way that requires a human to know the optimal arrangement is if the object is bigger than 64 bytes and we're arranging fields based on access pattern (not optimal padding) -- in which case it might be a more human endeavor (requires understanding critical paths, some of which is information a compiler can't possibly anticipate without knowing what users will do with the software).

If not, could people give examples of what tricks you can use in Java
  (besides simple compiler flags).

The biggest difference to me in terms of an optimizing mentality between Java and C++ is that C++ might allow you to use objects a little (teeny) bit more than Java in a performance-critical scenario. For example, C++ can wrap an integer to a class with no overhead whatsoever (benchmarked all over the place). Java has to have that metadata pointer-style+alignment padding overhead per object which is why Boolean is bigger than boolean (but in exchange providing uniform benefits of reflection and the ability to override any function not marked as final for every single UDT).

It's a little bit easier in C++ to control the contiguity of memory layouts across non-homogeneous fields (ex: interleaving floats and ints into one array through a struct/class), since spatial locality is often lost (or at least control is lost) in Java when allocating objects through the GC.

... but often the highest-performance solutions will often split those up anyway and use an SoA access pattern over contiguous arrays of plain old data. So for the areas that need peak performance, the strategies to optimize memory layout between Java and C++ are often the same, and will often have you demolishing those teeny object-oriented interfaces in favor of collection-style interfaces that can do things like hot/cold field splitting, SoA reps, etc. Non-homogeneous AoSoA reps seem kind of impossible in Java (unless you just used a raw array of bytes or something like that), but those are for rare cases where both sequential and random access patterns need to be fast while simultaneously having a mixture of field types for hot fields. To me the bulk of the difference in optimization strategy (at the general kind of level) between these two is moot if you are reaching for peak performance.

The differences vary quite a bit more if you are simply reaching for "good" performance -- there not being able to do as much with small objects like Integer vs. int can be a bit more of a PITA, especially with the way it interacts with generics. It's a bit harder to just build one generic data structure as a central optimization target in Java that works for int, float, etc. while avoiding those bigger and expensive UDTs, but often the most performance-critical areas will require hand-rolling your own data structures tuned for a very specific purpose anyway so it's only annoying for code that is striving for good performance but not peak performance.

Object Overhead

Note that Java object overhead (metadata and loss of spatial locality and temporary loss of temporal locality after an initial GC cycle) is often big for things that are really small (like int vs. Integer) which are being stored by the millions in some data structure that's largely contiguous and accessed in very tight loops. There seems to be a lot of sensitivity about this subject, so I should clarify that you don't want to be worrying about object overhead for big objects like images, just really minuscule objects like a single pixel.

If anyone feels doubtful about this part, I'd suggest making a benchmark between summing up a million random ints vs. a million random Integers and to do this repeatedly (the Integers will reshuffle in memory after an initial GC cycle).

Ultimate Trick: Interface Designs That Leave Room to Optimize

So the ultimate Java trick as I see it if you are dealing with a place that handles a heavy load over small objects (ex: a Pixel, a 4-vector, a 4x4 matrix, a Particle, possibly even an Account if it only has a few small fields) is to avoid using objects for these teeny things and use arrays (possibly chained together) of plain old data. The objects then become collection interfaces like Image, ParticleSystem, Accounts, a collection of matrices or vectors, etc. Individual ones can be accessed by index, e.g. This is also one of the ultimate design tricks in C and C++, since even without that basic object overhead and disjointed memory, modeling the interface at the level of a single particle prevents the most efficient solutions.

Body:
[...] (granted, in the microsecond environment) [...]

Micro-seconds add up if we're looping over millions to billions of things. A personal vtune/micro-optimization session from C++ (no algorithmic improvements):

T-Rex (12.3 million facets):
Initial Time: 32.2372797 seconds
Multithreading: 7.4896073 seconds
4.9201039 seconds
4.6946372 seconds
3.261677 seconds
2.6988536 seconds
SIMD: 1.7831 seconds
4-valence patch optimization: 1.25007 seconds
0.978046 seconds
0.970057 seconds
0.911041 seconds

Everything besides "multithreading", "SIMD" (handwritten to beat the compiler), and the 4-valence patch optimization were micro-level memory optimizations. Also the original code starting from the initial times of 32 seconds was already optimized quite a bit (theoretically-optimal algorithmic complexity) and this is a recent session. The original version long before this recent session took over 5 minutes to process.

Optimizing memory efficiency can help often by anywhere from several times to orders of magnitudes in a single-threaded context, and more in multithreaded contexts (the benefits of an efficient memory rep often multiply with multiple threads in the mix).

On the Importance of Micro-Optimization

I get a little agitated by this idea that micro-optimizations are a waste of time. I agree that it's good general advice, but not everyone does it incorrectly based on hunches and superstitions rather than measurements. Done correctly, it doesn't necessarily yield a micro impact. If we take Intel's own Embree (raytracing kernel) and test only the simple scalar BVH they've written (not ray packet which is exponentially harder to beat), and then try to beat the performance of that data structure, it can be a most humbling experience even for a veteran used to profiling and tuning code for decades. And it's all because of micro-optimizations applied. Their solution can process over a hundred million rays per second when I've seen industrial professionals working in raytracing who can't even get more than 3 million rays per second on the same hardware (same bounding volume hierarchy, same logarithmic search).

There's no way to take a straightforward implementation of a BVH with only an algorithmic focus and get over a hundred million primary ray intersections per second out of it against any optimizing compiler (even Intel's own ICC). A straightforward one often doesn't even get a million rays per second. It takes professional-quality solutions to often even get a few million rays per second. It takes Intel-level micro-optimization to get over a hundred million rays per second.

Algorithms

I think micro-optimization isn't important as long as performance isn't important at the level of minutes to seconds, e.g., or hours to minutes. If we take a horrific algorithm like bubble sort and use it over a mass input as an example, and then compare it to even a basic implementation of merge sort, the former might take months to process, the latter maybe 12 minutes, as a result of quadratic vs linearithmic complexity.

The difference between months and minutes is probably going to make most people, even those not working in performance-critical fields, consider the execution time to be unacceptable if it requires users waiting for months to get a result.

Meanwhile, if we compare the non-micro-optimized, straightforward merge sort to quicksort (which is not at all algorithmically superior to merge sort, and only offers micro-level improvements for locality of reference), the micro-optimized quicksort might finish in 15 seconds as opposed to 12 minutes. Making users wait 12 minutes might be perfectly acceptable (coffee break kind of time).

I think this difference is probably negligible to most people between, say, 12 minutes and 15 seconds, and that's why micro-optimization is often considered useless since it's often only like the difference between minutes and seconds, and not minutes and months. The other reason I think it's considered useless is that it's often applied to areas that don't matter: some little area which isn't even loopy and critical which yields some questionable 1% difference (which may very well just be noise). But for people who care about these types of time differences and are willing to measure and do it right, I think it's worth paying attention to at least the basic concepts of the memory hierarchy (specifically the upper levels relating to page faults and cache misses).

Java Leaves Plenty of Room for Good Micro-Optimizations

Phew, sorry -- with that sort of rant aside:

Does the "magic" of the JVM hinder the influence a programmer has over
  micro-optimisations in Java?

A little bit but not as much as people might think if you do it right. For example, if you are doing image processing, in native code with handwritten SIMD, multithreading, and memory optimizations (access patterns and possibly even representation depending on image processing algorithm), it's easy to crunch hundreds of millions of pixels per second for 32-bit RGBA pixels (8-bit color channels) and sometimes even billions per second.

It's impossible to get anywhere close in Java if you say, made a Pixel object (this alone would inflate the size of a pixel from 4 bytes to 16 on 64-bit).

But you might be able to get a whole lot closer if you avoided the Pixel object, used an array of bytes, and modeled an Image object. Java's still pretty competent there if you start using arrays of plain old data. I've tried these kinds of things before in Java and was quite impressed provided that you don't create a bunch of little teeny objects everywhere that are 4 times bigger than normal (ex: use int instead of Integer) and start modeling bulk interfaces like an Image interface, not Pixel interface. I'd even venture to say that Java can rival C++ performance if you are looping over plain old data and not objects (huge arrays of float, e.g., not Float).

Perhaps even more important than the memory sizes is that an array of int guarantees a contiguous representation. An array of Integer does not. Contiguity is often essential for locality of reference since it means multiple elements (ex: 16 ints) can all fit into a single cache line and potentially be accessed together prior to eviction with efficient memory access patterns. Meanwhile a single Integer might be stranded somewhere in memory with surrounding memory being irrelevant, only to have that region of memory loaded into a cache line only to use a single integer prior to eviction as opposed to 16 integers. Even if we got marvelously lucky and surrounding Integers were all right next to each other in memory, we can only fit 4 into a cache line that can be accessed prior to eviction as a result of Integer being 4 times larger, and that's in the best-case scenario.

And there's plenty of micro-optimizations to be had there since we're unified under the same memory architecture/hierarchy. Memory access patterns matter no matter what language you use, concepts like loop tiling/blocking might be generally applied far more often in C or C++, but they benefit Java just as much.

I recently read in C++ sometimes the ordering of the data members can
  provide optimizations [...]

The order of data members generally don't matter in Java, but that's mostly a good thing. In C and C++, preserving the order of data members is often important for ABI reasons so compilers don't mess with that. Human developers working there have to be careful to do things like arrange their data members in descending order (largest to smallest) to avoid wasting memory on padding. With Java, apparently the JIT can reorder the members for you on the fly to ensure proper alignment while minimizing padding, so provided that's the case, it automates something that average C and C++ programmers can often do poorly and end up wasting memory that way (which isn't just wasting memory, but often wasting speed by increasing the stride between AoS structures needlessly and causing more cache misses). It's a very robotic thing to rearrange fields to minimize padding, so ideally humans don't deal with that. The only time where field arrangement might matter in a way that requires a human to know the optimal arrangement is if the object is bigger than 64 bytes and we're arranging fields based on access pattern (not optimal padding) -- in which case it might be a more human endeavor (requires understanding critical paths, some of which is information a compiler can't possibly anticipate without knowing what users will do with the software).

If not, could people give examples of what tricks you can use in Java
  (besides simple compiler flags).

The biggest difference to me in terms of an optimizing mentality between Java and C++ is that C++ might allow you to use objects a little (teeny) bit more than Java in a performance-critical scenario. For example, C++ can wrap an integer to a class with no overhead whatsoever (benchmarked all over the place). Java has to have that metadata pointer-style+alignment padding overhead per object which is why Boolean is bigger than boolean (but in exchange providing uniform benefits of reflection and the ability to override any function not marked as final for every single UDT).

It's a little bit easier in C++ to control the contiguity of memory layouts across non-homogeneous fields (ex: interleaving floats and ints into one array through a struct/class), since spatial locality is often lost (or at least control is lost) in Java when allocating objects through the GC.

... but often the highest-performance solutions will often split those up anyway and use an SoA access pattern over contiguous arrays of plain old data. So for the areas that need peak performance, the strategies to optimize memory layout between Java and C++ are often the same, and will often have you demolishing those teeny object-oriented interfaces in favor of collection-style interfaces that can do things like hot/cold field splitting, SoA reps, etc. Non-homogeneous AoSoA reps seem kind of impossible in Java (unless you just used a raw array of bytes or something like that), but those are for rare cases where both sequential and random access patterns need to be fast while simultaneously having a mixture of field types for hot fields. To me the bulk of the difference in optimization strategy (at the general kind of level) between these two is moot if you are reaching for peak performance.

The differences vary quite a bit more if you are simply reaching for "good" performance -- there not being able to do as much with small objects like Integer vs. int can be a bit more of a PITA, especially with the way it interacts with generics. It's a bit harder to just build one generic data structure as a central optimization target in Java that works for int, float, etc. while avoiding those bigger and expensive UDTs, but often the most performance-critical areas will require hand-rolling your own data structures tuned for a very specific purpose anyway so it's only annoying for code that is striving for good performance but not peak performance.

Object Overhead

Note that Java object overhead (metadata and loss of spatial locality and temporary loss of temporal locality after an initial GC cycle) is often big for things that are really small (like int vs. Integer) which are being stored by the millions in some data structure that's largely contiguous and accessed in very tight loops. There seems to be a lot of sensitivity about this subject, so I should clarify that you don't want to be worrying about object overhead for big objects like images, just really minuscule objects like a single pixel.

If anyone feels doubtful about this part, I'd suggest making a benchmark between summing up a million random ints vs. a million random Integers and to do this repeatedly (the Integers will reshuffle in memory after an initial GC cycle).

Ultimate Trick: Interface Designs That Leave Room to Optimize

So the ultimate Java trick as I see it if you are dealing with a place that handles a heavy load over small objects (ex: a Pixel, a 4-vector, a 4x4 matrix, a Particle, possibly even an Account if it only has a few small fields) is to avoid using objects for these teeny things and use arrays (possibly chained together) of plain old data. The objects then become collection interfaces like Image, ParticleSystem, Accounts, a collection of matrices or vectors, etc. Individual ones can be accessed by index, e.g. This is also one of the ultimate design tricks in C and C++, since even without that basic object overhead and disjointed memory, modeling the interface at the level of a single particle prevents the most efficient solutions.


问:
An ideal way to decode JSON documents in C?
Assuming I have an API to consume that uses JSON as a data transmission method, what is an ideal way to decode the JSON returned by each API resource? For example, in Java I'd create a class for each API resource then initiate an object of that class and consume data from it.

for example:

```<code>class UserJson extends JsonParser
{
    public function UserJson(String document) {
    /*Initial document parsing goes here...*/
    }
//A bunch of getter methods . . . .
}
</code>```

The probably do something like this:

```<code>UserJson userJson = new UserJson(jsonString);//Initial parsing goes in the constructor
String username = userJson.getName();//Parse JSON name property then return it as a String.
</code>```

Or when using a programming language with associative arrays(i.e., hash table) the decoding process doesn't require creating a class:

(PHP)

```<code>$userJson = json_decode($jsonString);//Decode JSON as key=>value
$username = $userJson['name'];
</code>```

But, when I'm programming in procedural programming languages (C), I can't go with either method, since C is neither OOP nor supports associative arrays(by default, at least).

What is the "correct" method of parsing pre-defined JSON strings(i.e., JSON documents specified by the API provider via examples or documentation)?

The method I'm currently using is creating a file for each API resource to parse, the problem with this method is that it's basically a lousy version of the OOP method, as it looks exactly like the OOP method but doesn't provide any OOP benefits(e.g., can't pass an object of the parser, etc.).

I've been thinking about encapsulating each API resource parser file in a publicly accessed structure(pointing all functions/publicly usable variables to the structure) then accessing the parser file code from within the structure(parser.parse(), parser.getName(), etc.). As this way looks a bit better than the my current method, it still just a rip off the OOP way, isn't it?

Any suggestions for methods to parse JSON documents on procedural programming lanauges? Any comments on the methods I'm currently using(either 3 of them)?

答:
I had the same problem. I have fixed c structures, and wanted to import/export to/from json objects/arrays. The resulting library is here: https://github.com/jamie-pate/jstruct and uses https://github.com/json-c/json-c for the actual json parse/stringify.

It works by allowing you to add annotations to your c struct headers, then parsing the headers and generating metadata that allows it to align the json with c structs for one line import/export.

```<code>//@json
struct my_my_json_data {
    /*
    @schema {
        "title": "ID",
        "description": "unique object id",
        "type": "int"
    }
    */
    uint64_t id;

    /* don't include in json */
    //@private
    int _id;

    bool active;
}
</code>```

Body:
I had the same problem. I have fixed c structures, and wanted to import/export to/from json objects/arrays. The resulting library is here: https://github.com/jamie-pate/jstruct and uses https://github.com/json-c/json-c for the actual json parse/stringify.

It works by allowing you to add annotations to your c struct headers, then parsing the headers and generating metadata that allows it to align the json with c structs for one line import/export.

//@json
struct my_my_json_data {
    /*
    @schema {
        "title": "ID",
        "description": "unique object id",
        "type": "int"
    }
    */
    uint64_t id;

    /* don't include in json */
    //@private
    int _id;

    bool active;
}