Keeping those headers aligned

One dead give-away of a GNOME/Gtk programmer is how they format their headers. For the better part of two decades, many of us have been trying to keep things aligned. Whether this is cargo-culted or of real benefit depends on the reader. Generally, I find them easier to filter through.

Unfortunately, none of indent, clang-format, nor uncrustify have managed to exactly represent our style which makes automated code formatting tools rather problematic. Especially in an automated fashion.

For example, notice how the types and trailing asterisks, stay aligned, in multiple directions.

FOO_EXPORT
void   foo_do_something_async  (Foo                  *self,
                                const gchar * const  *params,
                                GCancellable         *cancellable,
                                GAsyncReadyCallback   callback,
                                gpointer              user_data);
FOO_EXPORT
Bar   *foo_do_something_finish (Foo                  *self,
                                GAsyncResult         *result,
                                GError              **error);

Keeping that sort of code aligned is quite a pain. Even for vim users who can fairly easily repeat commands. Worse, it can explode patches into unreadable messiness.

Anyway, I added a new command in Builder last night that will format these in this style so long as you don’t do anything to trip it up. Just select a block of function declarations, and run format-decls from the command bar.

It doesn’t yet handle vtable entries, but that shouldn’t be too painful. Also, it doesn’t handle miscellaneous other C code in-between declarations (except G_GNUC_* macros, __attribute_() etc.

A new completion engine for Builder

Since my initial announcement of Builder at GUADEC in 2014, I’ve had a vision in the back of my mind about how I’d like completion to work in Builder. However, there have been more important issues to solve and I’m just one person. So it was largely put on the back burner because after a few upstream patches, the GtkSourceView design was good enough.

However, as we start to integrate more external tooling into Builder, the demands and design of what those completion layers expect of the application have changed. And some of that is in conflict with the API/ABI we have in the long-term stable versions of GtkSourceView.

So over the past couple of weeks, I’ve built a new completion engine for Builder that takes these new realities into account.

A screenshot of Builder's new completion engine showing results from clang in a C source file.

It has a number of properties I wanted for Builder such as:

Reduced Memory and CPU Usage

Some tooling wants to give you a large set of proposals for completion and then expects the IDE to filter in the UI process. Notably, this is how Clang works. That means that a typical Gtk application written in C could easily have 25,000 potential completion proposals.

In the past we mitigated this through a number of performance tricks, but it still required creating thousands of GObjects, linked lists, queues, and such. That is an expensive thing to do on a key-press, especially when communicating with a sub-process used for crash-isolation.

So the new completion provider API takes advantage of GListModel which is an interface that focuses on how to have a collection of GObjects which don’t need to be “inflated” until they’ve been requested. In doing so, we can get our GVariant IPC message from the gnome-builder-clang sub-process as a single allocation. Then, as results are requested by the completion display, a GObject is inflated on demand to reference an element of that larger GVariant.

In doing so, we provide a rough upper bound on how many objects need to be created at any time to display the results to the user. We can also still sort and filter the result set without having to create a GObject to represent the proposal. That’s a huge win on memory allocator churn.

Consistent and Convenient Refiltering

Now that we have external tooling that expects UI-side refiltering of proposals, we need to make that easier for tooling to do without having to re-query. So the fuzzy search and highlighting tools have been moved into IdeCompletion for easy access by completion providers.

As additional text is provided for completion, the providers are notified to perform filters on their result set. Since the results are GListModel-based, everything updates in the UI out-of-band nicely with a minimal number of gsignal emissions. Compare this to GtkTreeModel which has to emit signals for every row insertion, change, or deletion!

Alternative Styling

When working with completions for programming languages, we’re often dealing with 3 potential groups of content. The return value, the name and possible parameters, and miscellaneous data. To get the styling we want for all of this, I chose to forgo the use of GtkTreeView and use widgets directly. That means that we can use CSS like we do everywhere else. But also, it means that some additional engineering is required.

We only want to create widgets for the visible rows, because otherwise we’re wasting memory and time crunching CSS for things that won’t be seen. We also want to avoid creating new widgets every time the visible range of proposals is changed.

The result is IdeCompletionListBox which is a GtkBox containing GtkListBoxRow and some GtkSizeGroups to give things a columnar effect. Because the number of created widgets is small things stay fast and snappy while giving us the desired effect. Notably, it implements GtkScrollable so if you place it in a GtkScrolledWindow you still get the expected behavior.

Further more, we can adjust the window sizing and placement to be more natural for code-related proposals.

Dynamic Priority Control

We want the ability to change the priority of some completion providers based on the context of the completion. The new design allows for providers to increase their priority when they know they have something of high-importance given some piece of contextual knowledge.

Long term, we also want to provide an API for providers to register a small number of suggested completions that will be raised to the top-level, regardless of what provider gave them. This is necessary instead of having global “scoring” since that would require both O(n) scans of the data set as well as coming up with a strategy to score disparate systems (and search engines prove that rarely works well).

More to do

There are still a couple things that I think we should address that may influence the API design more. For example:

  • How should we handle string interpolation? A simplified API for completions when working inside of strings might be useful. Think strftime(), printf(), etc as potential examples here.
  • The upcoming Gtk+ 3.24 release will give us access to the move_to_rect() API. Combined with some Wayland xdg_popup improvements, this could allow us to make our display widget more flexible.
  • Parameter completion is still a bit of an annoying process. We could probably come up with a strategy to make the display look a lot better here.
  • Give some tweaks and knobs for how much and what to complete (just function name vs parameters and types).

Conclusions

Rarely do I write any code that doesn’t have bugs. Now that this is landing in Builder Nightly soon, I could use some more testing and bug filing from the community at large.

I’m very happy with the improvements over the past couple of months. Between getting Clang out of process and this to allow us to make clang completion fast, I think we’re in a much better place.

We can’t get this design into older GtkSourceView releases, but we can probably look at some form of integration into what will eventually integrate with Gtk4. I would be very happy if it influenced new API releases of the library so that we don’t need to carry the implementation downstream.

Compiler complexities

The other day I found myself perusing through some disassembly to get an idea of the code’s complexity. I do that occasionally because I find it the quickest way to determine if something is out of whack.

While I was there, I noticed a rather long _get_type() function. It looked a bit long and more importantly, I only saw one exit point (retq instruction on x86_64).

That piqued my interest because _get_type() functions are expected to be fast. In the fast-path (when they’ve already been registered), I’d expect them to check for a non-zero static GType type_id and if so return it. That is just a handful of instructions at most, so what gives?

The first thing that came to mind is that I use -O0 -g -fno-omit-frame-pointer on my local builds so that I get good debug symbols and ensure that Linux-perf can unwind the stack when profiling. So let’s disable that.

Now I’ve got everything rebuilt with the defaults (-O2 -fomit-frame-pointer). Now I see a couple exit points, but still what appears to be too many for the fast path and what is this __stack_chk_fail@plt I see?

A quick search yields some information about -fstack-protector which is a recent (well half-decade) compiler feature that employs various tricks to detect stack corruption. Distributions seem to enable this by default using -fstack-protector-strong. That tries to only add stack checks to code it thinks is accessing stack allocated data.

So quick recompile with -fno-stack-protector to disable the security feature and sure enough, a proper fast path emerges, We drop from 15 instructions (with 2 conditional jumps) to 5 instructions (with 1 conditional jump).

So the next question is: “Well okay, is this worth making faster?”

That’s a complicated question. The code was certainly faster before that feature was enabled by default. The more instructions you execute, the more code has to be loaded into the instruction cache (which is very small). To load instructions means pushing others out. So even if the code itself isn’t much faster, it can prevent the surrounding code from being faster.

But furthermore, we do a lot of _get_type() calls. They are used when doing function precondition checks, virtual methods, signals, type checks, interface lookups, checking a type for conformance, altering the reference count, marshaling data, accessing properties, … you get the idea.

So I mucked through about 5 different ways trying to see if I could make things faster without disabling the stack protector, without much luck. The way types are registered access some local data via macros. Nothing seemed to get me any closer to those magic 5 instructions.

GCC, since version 4.4, has allowed you to disable the stack-protector on a per-function basis. Just add __attribute__((optimize("no-stack-protector"))) to the function prototype.

#if G_GNUC_CHECK_VERSION(4, 4)
# define G_GNUC_NO_STACK_PROTECTOR \
  __attribute__((optimize("no-stack-protector")))
#else
# define G_GNUC_NO_STACK_PROTECTOR
#endif

GType foo_get_type (void) G_GNUC_NO_STACK_PROTECTOR;

Now we get back to our old (faster) version of the code.

 48 8b 05 b9 15 20 00    mov    0x2015b9(%rip),%rax   
 48 85 c0                test   %rax,%rax
 74 0c                   je     400ac8
 48 8b 05 ad 15 20 00    mov    0x2015ad(%rip),%rax   
 c3                      retq   

But what’s the difference you ask?

I put together a test that I can run on a number of machines. It was unilaterally faster in each case (as expected), but some by as much as 50% (likely due to various caches).

Arch OS Type Speedup
ARM Ubuntu 14.04 Odroid X2 +24%
x64_64 Fedora 28 X1 Carbon Gen3 +25.5%
x86_64 Fedora 28 i7 gen7 NUC +12.25%
x86_64 Fedora 28 Surface Book 2 i7 (gen8) +12.5%
x86_64 Fedora 27 Onda Tablet +50.6%
x86 Debian netbook +12.5%

It’s my opinion that one place where it makes sense to keep things very fast (and reduce instruction cache blow-out) is a type system. That code gets run a lot intermixed between all the code you really care about.

GTask and Threaded Workers

GTask is super handy, but it’s important you’re very careful with it when threading is involved. For example, the normal threaded use case might be something like this:

state = g_slice_new0 (State);
state->frob = get_frob_state (self);
state->baz = get_baz_state (self);

task = g_task_new (self, cancellable, callback, user_data);
g_task_set_task_data (task, state, state_free);
g_task_run_in_thread (task, state_worker_func);

The idea here is that you create your state upfront, and pass that state to the worker thread so that you don’t race accessing self-> fields from multiple threads. The “shared nothing” approach, if you will.

However, even this isn’t safe if self has thread usage requirements. For example, if self is a GtkWidget or some other object that is expected to only be used from the main-thread, there is a chance your object could be finalized in a thread.

Furthermore, the task_data you set could also be finalized in the thread. If your task data also holds references to objects which have thread requirements, those too can be unref’d from the thread (thereby cascading through the object graph should you hit this undesirable race).

Such can happen when you call g_task_return_pointer() or any of the other return variants from the worker thread. That call will queue the result to be dispatched to the GMainContext that created the task. If your CPU task-switches to that thread before the worker thread has released it’s reference you risk the chance the thread holds the last reference to the task.

In that situation self and task_data will both be finalized in that worker thread.

Addressing this in Builder

We already have various thread pools in Builder for work items so it would be nice if we could both fix the issue in our usage as well as unify the thread pools. Additionally, there are cases where it would be nice to “chain task results” to avoid doing duplicate work when two subsystems request the same work to be performed.

So now Builder has IdeTask which is very similar in API to GTask but provides some additional guarantees that would be very difficult to introduce back into the GTask implementation (without breaking semantics). We do this by passing the result and the threads last ownership reference to the IdeTask back to the GMainContext at the same time, ensuring the last unref happens in the expected context.

While I was at it, I added a bunch of debugging tools for myself which caught some bugs in my previous usage of GTask. Bugs were filed, GTask has been improved, yadda yadda.

But I anticipate the threading situation to remain in GTask and you should be aware of that if you’re writing new code using GTask.

g_object_ref and -Wincompatible-pointer-types

I proposed a change to GObject that was merged not too long ago that uses __typeof__ on GCC/Clang to propagate the pointer type from the parameter. For example, the old prototype was something like:

gpointer g_object_ref (gpointer instance);

Which meant you got a cast for free even if you made a mistake such as:

FooBar *bar = foo_bar_new ();
FooFrob *frob = g_object_ref (bar);

But now, we propagate the type of the parameter as the return value with a macro that is essentially:

#define g_object_ref(Obj)  ((__typeof__(Obj)) (g_object_ref) (Obj))

Now, the code example above would be an -Wincompatible-pointer-types warning from GCC/Clang. This isn’t a common problem (people often rely on this implicit cast when using inheritance). However, when you do make the mistake it’s rather annoying to track down. I’ve certainly made the mistake before when too-quickly copying lines of code, and I know I’m not the only one.

So, how do you fix the warnings in your code base if you were relying on the implicit cast? Both of these will work, I have a preference for the former.

FooFrob *frob = g_object_ref (FOO_FROB (bar));
FooFrob *frob = FOO_FROB (g_object_ref (bar));

Builder gains multi-touch gestures

If you’re running Wayland and have a touchpad capable of multi-touch, Builder (Nightly) now lets you do fun stuff like the following video demonstrates.

Just three-finger-swipe left or right to move the document. Content is sticky-to-fingers, which is my expectation when using gestures.

It might also work on a touchscreen, but I haven’t tried.

Modern Text Editor Design

I’ve been fascinated about a few technologies in my career. I have a fondness for finding the right data-structure for a problem. Maybe it was because of all those years playing with cars that gave me the “I wanna go fast” mentality. It lead me to various jobs, including working on databases.

Another technology I love are text editors. There is some really fascinating technology going on behind the scenes.

Gtk4 development is heating up, and we are starting to see a toolkit built like a game engine. That’s pretty cool. But how will that change how we write editors? Should it?

In the Gtk3 cycle, I added support to GtkTextView that would render using Alex’s GtkPixelCache. It helped us amortize the cost of rendering into mostly just an XCopyArea() when drawing a frame. It’s why we have that nice 60fps two-finger-scrolling.

But now that we can have GPU textures, do we want to start doing paginated rendering like Apple did with Preview to make PDF rendering ultra fast? Do we want to focus on just sending text data to the GPU to render from an glyph atlas? How about layout? And intermixing right-aligned with left-aligned text? What if we just focus on code editing and not generic editing with rich font support. How about inserting widgets in-between rows? Do we want unlimited undo? How about crash recovery?

These are all questions that can inform the design of a text editor, and they are things I’m starting to think about.

To inform myself on the problem domain better, I started writing a piecetable implementation with various tweaks to outperform those I’ve seen previously. What I’ve come up with is a combination of a b+tree (bplus tree) and a piecetable. The neat thing about it is the high-density you get per-cacheline as compared to something in a RBTree or SplayTree (Atom recently did this, and AbiWord did it a decade ago). It’s at least as fast as those, but with much less malloc overhead because you need fewer, but densely packed allocations.

I prefer dense-cacheline packed structures over pointer chasing (dereferencing pointers) because the CPU can crunch through numbers in a cacheline much faster than it can load another cacheline (as it may not yet be in L1-3 caches). So while it looks like you’re doing more work, you may in fact be saving time.

On my 10 year old 1.2ghz ThinkPad, I can do 1.5 to 2 million random inserts per-second. So I think it’s “good enough” to move on to solving the next layer of problems.

One neat thing about using the linked-leaves from a b+tree is that you get a “next pointer” from each leaf to the next sequential leaf. So if you need to reconstruct the buffer, it’s a simple scan without tree traversal. This is a common problem in a text editor, because we’re sending out text data to diagnostic engines constantly and it needs to be optimized for.

Part of the piecetable design is that you have two buffers. The original data (file state at loading) and change data (append only buffer if each character typed by the user). The piece table is just pointing to ranges in each buffer set to reconstruct the final buffer.

If you log all of your operations to a log file, you can fairly quickly get yourself a crash recovery mechanism. Additionally, you can create unlimited undo.

One thing I don’t like about GtkTextBuffer today is that you cannot open “very large files” with it. It can certainly handle 100mb text files, but it has to load all of that data into memory. And that means that opening a 10gb SQL dump is going to be fairly difficult. But if we implemented on-demand, paginated data loading (reading from disk when that portion of the file is needed), we can get a fixed memory overhead for a file.

One downside to that approach is that if the file is modified behind the scenes, you are basically screwed. (A proper rename() would not affect things since the old FD would still be valid). One way to work around this is to copy the file before editing (a swap file). If your filesystem has reflink support, that copy is even “free”.

Some files are in encodings that require conversion to UTF-8. If a character encoding crossed the page/block boundary, we’d not be able to convert it without locating the neighboring page. So it seems somewhat at odds with this design. But if we just do the iconv (or similar) encoding conversion as part of the copy to our swap file, you can ensure you have valid UTF-8 to begin with. It’s also a convenient place to count new lines so that you can get relatively accurate document height from the start (otherwise you have to scan the data and count newlines which will jump the scrollbar around).

Another thing that might be an interesting trick is to keep around PangoLayouts for each of the cursor lines. It might allow us to mutate the layout immediately upon the key-press-event and render the content out of order (without going through layout cycles). This is somewhat similar to what other editors do to make things “feel” more interactive. It guarantees you render the key event on the next frame, even if slightly incorrect.

In short, writing a good, fast, modern text editor today is the combination of writing a database and a graphics engine. Btrees, low-cardinality indexes, page caches, write ahead logs, transaction replays, memory pooling, GPU dispatching, texture atlases, layout, and more.

https://github.com/chergert/pieceplustree

Implementing GActionGroup

Gtk applications are more and more using GAction and GActionGroup and it’s easy to see why. They are stateful, allow parameters when activating, and can be inserted into the widget hierarchy using gtk_widget_insert_action_group(). The latter is useful so that you only activate actions (or toggle button sensitivity) in the portion of the user interface that makes sense.

One thing to consider is what your strategy will be for using GActionGroup. One way is to encapsulate the GActionGroup by using GSimpleActionGroup. Another, which I prefer, is to implement the GActionGroupInterface. Although, this requires much more boilerplate code.

Until now…

In libdazzle, I added a header-only helper to ease creating action groups with much less effort on your part.

It goes something like this.

#include <dazzle.h>

#include "foo-bar.h"

static void foo_bar_action_frobnicate (FooBar   *self,
                                       GVariant *param);

DZL_DEFINE_ACTION_GROUP (FooBar, foo_bar, {
  { "frobnicate", foo_bar_action_frobnicate },
})

G_DEFINE_TYPE_WITH_CODE (FooBar, foo_bar, G_TYPE_OBJECT,
                         G_IMPLEMENT_INTERFACE (G_TYPE_ACTION_GROUP, foo_bar_init_action_group))

There are a few niceties when defining action groups this way.

  • Your function signatures get your proper class type as parameter 1.
  • You no longer need to instantiate a GSimpleAction for every action.
  • No unnecessary parameters (like user_data) need to be provided anymore.
  • It uses GActionGroupInterface.query_action to optimize for certain queries.
  • You can change action state with ${prefix}_set_action_state().
  • You can change if an action is enabled with ${prefix}_set_action_enabled().
  • You can take your new GActionGroup and gtk_widget_insert_action_group() directly.

That’s it for now, happy hacking!

Builder 3.25.5

Like every year, GUADEC has snuck up on me. I’ll be heading out to Manchester in a handful of days which means things are going to get hectic any moment now.

We just reached another milestone in our development phase towards 3.26. I’ve landed two important components which will have important roles in Builder’s future. The new visual layout, and the new shortcut engine. Neither are complete yet, but they are good enough to land on master and allow us to iterate without giant branches.

The new layout is based upon a design iteration lead by Allan which Andreas, Jakub, and myself took part. Not everything is implemented but the parts which most heavily contribute to user workflow are in place.

The new shortcut engine has also landed. This is a monumental amount of work because it completely overhauls the keyboard input model within Builder. We’ve moved to a “capture and bubble” event delivery for keyboard input so that we have more flexibility in how shortcuts are activated.

The event delivery is in one of three phases. Capture, Dispatch, or Bubble. The capture phase allows the widget hierarchy (starting from the toplevel) to handle an input event before the destination widget. Dispatch is delivery to the expected destination, where GtkBindingSets are activated. Finally, the bubble phase allows the hierarchy to handle the event if nothing handled it previously.

This also includes a whole swath of features around it for user-modifiable shortcut themes, custom keyboard controllers, a shortcut editor and more. To simplify the process of merging into Builder it has a compatibility interface to support CSS-based -gtk-key-bindings properties.

Effectively, bubble/capture allows us to have keyboard shortcuts that only activate if the source editor or terminal have not stolen the input. A convincing Vim implementation for our source editor can really benefit from this.

Enjoy some screenshots

This week in Builder

  • 3.25.3 releases of Builder, jsonrpc-glib, libdazzle, and template-glib.
  • Work is progressing for shortcuts and UI redesign on wip/chergert/layout
  • Features that the UI redesign depends on have landed in libdazzle. This includes animated widget transitions and more.
  • Builder’s Flatpak of Stable and Nightly channels now bundle OSTree 2017.7 and Flatpak 0.9.6 which should improve situations where we were failing to load summary files from the host.
  • A painful bug where Builder (Nightly Flatpak channel) would crash when launched from the Activities menu was fixed. This was a race condition that seemed to not happen when run from the command line. After some manual debugging the issue was fixed.
  • To simplify future debugging, we’ve added a “Bug Buddy” like feature. If you remember bug-buddy, you’re old like me. If Builder receives a SIGSEGV, we try to fork()/exec() an instance of gdb to inspect our process. It will dump a lot of useful information for us like where files are mapped in memory, instruction pointer addresses, and any callstack that can be discovered.
  • Libdazzle gained some new action muxer helpers to clean up action visibility.
  • The new editor (perspective, grid, columns, and view) design will help us drastically simplify some of Builder’s code. But this also needs forward-porting a bunch of plugins to the new design.
  • The new libdazzle based menu joiner landed to help us integrate contextual menus based on file content-type as GMenu does not support “conditionals” when displaying menus.
  • meson test should work again for running Builder’s unit tests under the Meson build system.
  • Anoop blogged about his work to add a code indexer to Builder here.
  • Lucie blogged about her work to make documentation easily accessible while you code here.
  • Umang blogged about his work to improve our word completion engine here.