Today's Reads

We’ve defined a bunch of objects related to polytabloids. Let’s see how they relate to permutations.

First of all, I say that

Indeed, what does it mean to say that \(\sigma\in R_{\pi t}\)? It means that \(\sigma\) preserves the rows of the tableau \(\pi t\). And therefore it acts trivially on the tabloid \(\{\pi t\}\). That is: \(\sigma\{\pi t\}=\{\pi t\}\). But of course we know that \(\{\pi t\}=\pi\{t\}\), and thus we rewrite \(\sigma\pi\{t\}=\pi\{t\}\), or equivalently \(\pi^{-1}\sigma\pi\{t\}=\{t\}\). This means that \(\pi^{-1}\sigma\pi\in R_t\), and thus \(\sigma\in\pi R_t\pi^{-1}\), as asserted.

Similarly, we can show that \(C_{\pi t}=\pi C_t\pi^{-1}\). This is slightly more complicated, since the action of the column-stabilizer on a Young tabloid isn’t as straightforward as the action of the row-stabilizer. But for the moment we can imagine a column-oriented analogue of Young tabloids that lets the same proof go through. From here it should be clear that \(\kappa_{\pi t}=\pi\kappa_t\pi^{-1}\).

Finally, I say that the polytabloid \(e_{\pi t}\) is the same as the polytabloid \(\pi e_t\). Indeed, we compute

December 24, 2010 - Posted by | Algebra, Representation Theory, Representations of Symmetric Groups

Discord is removing username discriminators, which got me thinking about usernames as a whole, and how to design a platform without them.

This post is written with discord in mind, but applies to basically any chat platform.

The only place where a user needs to interact with a username in discord is when adding a user as a friend. And discord already has a form of invite links, it just uses it to join servers rather than to invite users.

You could nuke usernames entirely. Users still have a unique identifier as normal, but that’s internal-only and not intended for use by anyone but discord and bots. Making user IDs private would be a good idea, but not the focus here. And have a display name which doesn’t have to be unique.

Now that usernames are gone, you need to have some way to add users. So introduce friend codes.

Friend codes act much like invite links to servers, in that they’re random codes that last for a specified length of time and uses, both of which can be infinite.

Codes should be human readable, writable, and memorable. People are shit with random letters, so instead make them words. 3 random words from a wordlist of 10000 gives you 10000³ possible codes, which is enough for 500 million users to have 2000 codes each. Therefore, a code would look like crude holders temp. You may also wish to use a wordlist that can correct for typos, and autocorrect on entry.

Codes should also be able to be in the user’s native language. This not only means people aren’t forced to memorise codes in English when they don’t speak it, but it also helps lower the usage of any specific wordlist, allowing more common words to be used.

The number of words in the wordlist doesn’t have to be fixed upfront, and can be changed on the fly. Shorter and more common words can be used for longer term codes, while longer words are used for temporary codes.

The use case of “I want someone to add me but I don’t have my phone with me” would be handled by encouraging generation of one permanent invite code. Depending on how many users use your system, this could be shortened to 2 words (100 million total codes with a wordlist of 10000). This is the closest thing to a username that this system would have, but is both not user selectable, and entirely optional. You would need to memorise the code, but in the current system you need to memorise your discriminator anyways, so no major difference. You can also very easily replace that invite code without affecting any other invite links, if it is being used to spam you.

Give the ability to give a name to codes, so you can have codes tied to a specific platform you put the code on. When you get a friend request, you’re told where the user got your code from, and you’re given the chance to revoke that code easily.

This change would mean that for every friend request you get, you’re able to know where it came from, and are given the ability to revoke it. You can also add a friend based on seeing a message from a user and clicking “Add Friend”. You should have the ability to be told which server the user added you from, and have the ability to block friend requests from that server.

If you have adding friend requests from servers disabled, and have no active invite links, there is no way for anyone to add you as a friend.

The above system both fixes issues with username squatting, and helps deal with spam issues where you can be told where someone added you from. No more message requests with Funny Images or death threats from randos. Or, at least, you can know how they know you.

This also works for federated systems, but you would need to add a server name to the invite codes, so codes would look like chat.5snb.club/sims bank tough. Bikeshed if you want a - instead of space there. And federated systems would likely use shorter codes because less users per server.

C and C++ perform implicit casts when, for example, you pass an integer-typed variable to a function that expects a different type. When the target type is wider, there’s no problem, but when the target type is narrower or when it is the same size and the other signedness, integer values may silently change when the type changes. For example, this program:

#include <iostream>

int main() {
  int x = -3;
  unsigned y = x;
  std::cout << y << "\n";
}

prints 4294967293. Like unsigned integer wraparound (and unlike signed integer overflow) these changes of value are not undefined behavior, but they may be unintentional and may also be bugs. As of recently, Clang contains support for dynamically detecting value changes and either providing a diagnostic or else terminating the program. Some fine-grained flags are available for controlling these diagnostics, but you can enable all of them (plus some others, such as signed overflow and unsigned wraparound checks) using -fsanitize=integer.

Now we get:

$ clang++ implicit2.cpp -fsanitize=integer
$ ./a.out 
implicit2.cpp:5:16: runtime error: implicit conversion from type 'int' of value -3 (32-bit, signed) to type 'unsigned int' changed the value to 4294967293 (32-bit, unsigned)
4294967293
$ 

Here’s a truncation example:

int main() {
  int x = 300;
  unsigned char c = x;
}

It gives:

$ clang++ implicit3.cpp -fsanitize=integer
$ ./a.out 
implicit3.cpp:3:21: runtime error: implicit conversion from type 'int' of value 300 (32-bit, signed) to type 'unsigned char' changed the value to 44 (8-bit, unsigned)
$

To suppress the diagnostic, we can make the conversion explicit using a cast:

int main() {
  int x = 300;
  unsigned char c = (unsigned char)x;
}

Different parts of this functionality landed in Clang before and after the 7.0.0 release — to get everything, you will want to build a Clang+LLVM from later than 1 Nov 2018 (or else wait for the 8.0.0 release in a few months).

How would you use these checks? Generally, they should be part of a testing campaign, perhaps in support of a code audit. If you enable them on a non-trivial code base, you will run into diagnostics that do not correspond to bugs, just because real C and C++ programs mix integer types so freely. I suggest starting with -fsanitize=implicit-integer-truncation. Let’s look at doing this to Clang+LLVM itself and then compiling a hello world program: here’s the output.

I’d be happy to hear about any interesting bugs located using these checks, if anyone wants to share.

Finally, see this tweet by Roman Lebedev (the author of these checks) showing that the runtime impact of -fsanitize-trap=implicit-conversion is very low.

As Java developers, we often face the challenge of handling very large datasets within the constraints of the Java Virtual Machine (JVM). When the heap size grows significantly—often beyond 32 GB—garbage collection (GC) pause times can escalate, leading to performance degradation. This article explores how Chronicle Queue enables the storage and efficient access of a 1 TB dataset on a machine with only 64 GB of RAM.

The Challenge of Large Heap Sizes

Using standard JVMs like Oracle HotSpot or OpenJDK, increasing the heap size to accommodate large datasets can result in longer GC pauses. These pauses occur because the garbage collector requires more time to manage the larger heap, which can negatively impact application responsiveness.

One solution is to use a concurrent garbage collector, such as the one provided by Azul Zing, designed to handle larger heap sizes while reducing GC pause times. However, this approach may only scale well when the dataset is within the available main memory.

Handling Datasets Larger Than Main Memory

What if your dataset is larger than your machine's main memory? In such cases, relying on the heap is not feasible. Off-heap data stores become essential. While databases or NoSQL solutions can handle large datasets, they often introduce significant latency, which may not be acceptable for high-performance applications.

Introducing Chronicle Queue

Chronicle Queue provides a persisted, off-heap data store that can be accessed by multiple JVMs on the same server. It leverages memory-mapped files to manage large datasets efficiently. But how does it perform when the dataset size exceeds the available RAM?

In this article, we'll examine Chronicle Queue's performance when handling a 1 TB dataset on a machine with 64 GB of memory, focusing on sequential access patterns.

What Does a 1 TB JVM Look Like?

First, let's see what a JVM managing over 1 TB of data looks like on a machine with 64 GB of RAM.

In the top output above, the JVM's virtual memory size (VIRT) is reported as 1,045.8 g, while the resident set size (RES) is only 50.0 g. This means that although the JVM addresses over 1 TB of data, only about 50 GB is actually loaded into physical memory at any given time. This is possible because Chronicle Queue uses memory-mapped files, allowing the operating system to handle virtual memory efficiently.

Performance Analysis: Does It Slow Down?

A common concern is that managing datasets larger than the main memory will degrade performance dramatically. If you attempted to create a 1 TB heap on a 64 GB machine, the JVM would likely fail to start or render the machine unusable due to excessive swapping. However, Chronicle Queue's off-heap approach minimizes this issue.

Writing and Reading Data

In our test, we perform the following steps:

• Write bursts of 1 GB consisting of 1 KiB messages.
• Perform a sync operation to flush data to disk.
• Read the data back sequentially.

The underlying disk can sustain about 630 MB/s. Writing 1 GB of data takes consistently less than 2 seconds, even as the total dataset size grows beyond the physical memory limit.

Consistent Write Performance

Minimal Write Slowdown

Writing 1 GB of data takes:

• An average of 1.3 seconds for the first 64 GB.
• An average of 1.5 seconds beyond 64 GB.

The slight increase in write time is minimal considering the dataset size and is acceptable for applications requiring high throughput.

Comparison with Traditional Databases

Consider the alternative of inserting 1 million records (approximately 1 GB) into a traditional database and querying them back. This process would likely take significantly longer and consume more resources. With Chronicle Queue, you can read 1 GB of records in around 70 ms using a single thread, offering a substantial performance advantage.

Conclusion

Chronicle Queue performs exceptionally well when handling datasets that exceed the main memory size. It maintains low GC pause times and efficient data access speeds by utilising off-heap memory and memory-mapped files. This makes it an ideal solution for large data volume processing applications without significant performance penalties.

Try It Yourself

You can experiment with this test by accessing the following code: RunLargeQueueMain.java

For more information on Chronicle Queue, visit the GitHub repository or the Chronicle Queue product page.

What Does the Enterprise Version Offer?

Chronicle Queue Enterprise offers additional features, such as:

• Replication across multiple servers for Fail Over and Disaster Recovery
• C++, Rust, Python implementations
• Tuning options to reduce latency jitter
• Support for Windows, macOS, and Linux

Share Your Thoughts

Have you faced challenges managing large datasets in Java? What solutions have you found effective? Feel free to share your experiences and join the discussion.

Note: Currently, having a queue larger than the main memory only works on Unix-based systems. On Windows, each cycle (e.g., a day's worth of data) must fit into the main memory. We aim to address this limitation in future updates.

During a recent Q&A session on Facebook, Mark Zuckerberg was asked a question by the famous cosmologist Stephen Hawking

I would like to know a unified theory of gravity and the other forces. Which of the big questions in science would you like to know the answer to and why?

Zuckerberg answered he was “most interested in questions about people,” and then began to provide some examples of his answer such as “What will enable us to live forever?” and “How can we empower humans to learn a million times more?” He then made this statement which reveals so much about himself:

I’m also curious about whether there is a fundamental mathematical law underlying human social relationships that governs the balance of who and what we all care about. I bet there is.

That's right. As Nicholas Carr surmises in his article, Zuckerburg believes all “human relations and affiliations can be reduced to equations”. Of course you can hardly blame him for believing this way. This is a man who has “made a fortune by seeing people as nodes in a mathematical graph”. Look at all the success, fame and fortune this way of thinking has brought him.

This new kind of behavioralism believes that big data around human behavior, in combination with sophisticated mathematical modeling and predictions, will provide a new set of rules by which new social systems will be more accurately engineered. But as Carr asks, these “better engineered social systems” are better for whom? And better by what measure?

In my opinion, this is so typical of modern thinking from technologists. We so easily confuse “the measurement of a phenomenon with the cause of the phenomenon”. We really seem to believe that if some data gives us a pattern, then more and more data will give us a fundamental law by which we can predict outcomes, even in something as unpredictable as humans.

But we humans aren’t so easily pigeonholed. While Zuckerberg is theorizing mathematically predicting and modeling the countlessly-nuanced biological emotions of human beings using computers, in practice we still haven’t discovered a reliable pattern for retrieving and storing a human’s name in a computer system:

John Graham-Cumming wrote an article today complaining about how a computer system he was working with described his last name as having invalid characters. It of course does not, because anything someone tells you is their name is — by definition — an appropriate identifier for them. John was understandably vexed about this situation, and he has every right to be, because names are central to our identities, virtually by definition… I have never seen a computer system which handles names properly and doubt one exists, anywhere.

Computers like rules, they live on patterns. When something breaks a pattern it’s an exception that has to be programmatically accounted for. And when it comes to humans, something as simple as our names is incredibly difficult to patternize for every single human being. Sure there are general rules that can be assumed but they don’t work for everyone everywhere. And that’s just with our names.

Can you imagine trying to pin down the edge cases for human emotion?