Posts tagged ‘Java’

At Least Python Got Equality Right

2013-01-03 23:13

I’m still flabbergasted after going through the analysis of PHP == operator, posted by my infosec friend Gynvael Coldwind. Up until recently, I knew two things about PHP: (1) it tries to be weakly typed and (2) it is not a stellar example of language design. Now I can confidently assert a third one…

It’s completely insane.

However, pondering the specific case of equality checks, I realized it’s not actually uncommon for programming languages to confuse the heck out of developers with their single, double or even triple “equals”. Among the popular ones, it seems to be a rule rather than exception.

Just consider that:

  • JavaScript has both == and ===, exactly like PHP does. And the former is just slightly less crazy than its PHP counterpart. For both languages, it just seems like a weak typing failure.
  • In C and C++, you may easily use = (assignment) in lieu of == (equality), because the former is perfectly allowed inside conditions for if, while or for statements.
  • Java is famously counterintuitive when it comes to comparing strings, requiring to use String.equals method rather than == (like in case of other fundamental data types). Many, many programmers have been bitten by that. (The fact that under certain conditions you can compare strings char-by-char with == doesn’t exactly help either).
  • C# complicates stuff even more by allowing to override Equals and overload == operator. It also introduces ReferenceEquals which usually works like ==, except when the latter is overloaded. Oh, and it also has two different kinds of types (value and reference types) which by default compare in two different ways… Joy!

The list could likely go on and include most of the mainstream languages but one of them would be curiously absent: Python.

You see, Python got the == operator right:

  • It tests for equality only, not identity (also known as “reference equality”). For that there is a separate is operator.
  • All basic objects – not only strings, but also lists or dictionaries (hash tables) – compare by value. Hence e.g. two lists are equal if they contain equal elements in the same order, whether or not they are the same objects.
  • Implicit conversions are applied judiciously. Different types of numbers (int, long, float) compare to each other just fine, but there is clear distinction between 42 (number) and "42" (string).
  • You can overload == but there are no magical tricks that instantly turn your class into wannabe fundamental type (like in C#). If you really want value semantics, you need to write that yourself.

In retrospect, all of this looks like basic sanity. Getting it right two decades ago, however… That’s work of genius, streak of luck – or likely both.

Tags: , , , , ,
Author: Xion, posted under Programming » 1 comment

Of Languages and Keywords

2012-05-28 18:40

I recently had a discussion with a co-worker about feasibility of using anonymous functions in Python. We happen to overuse them quite a bit and this is not something I’m particularly fond of. For me lambdas in Python are looking pretty weird and thus I prefer to use them sparingly. I wasn’t entirely sure why is it so – given that I’m quite a fan of functional programming paradigm – until I noticed a seemingly insignificant fact.

Namely: the lambda keyword is long. With six letters, it is among the longer keywords in Python 2.x, tied with return, import and global, and beaten only by continue and finally. Quite likely, this is what causes lambdas in Python to stand out and require additional mental resources to process (assuming we’re comfortable enough with the very idea of anonymous functions). The long lambda keyword seems slightly out of place because, in general, Python keywords are short.

Or are they?… Thinking about this, I’ve got an idea of comparing the average length of keywords from different programming languages. I didn’t really anticipate what kind of information would be exposed by applying such a metric but it seemed like a fun exercise. And it surely was; also, the results might provoke a thought or two.

Here they are:

Language Keyword Total chars Chars / keyword
Python 2.7 31 133 4.29
C++03 74 426 5.76
C++11 84 516 6.14
Java 1.7 50 289 5.78
C 32 166 5.19
C# 4.0 77 423 5.49
Go 25 129 5.16

The newest incarnation of C++ seems to be losing badly in this competition, followed by C#. On the other side of the spectrum, Go and Python seem to be deliberately designed to avoid keyword bloat as much as possible. Java is somewhere in between when it comes to sheer numbers of keywords but their average length is definitely on the long side. This could very well be one of the reasons for the perceived verbosity of the language.

For those interested, the exact data and code I used to obtain these statistics are in this gist.

Tags: , , , , ,
Author: Xion, posted under Computer Science & IT » 8 comments

Using Executors in Java

2012-01-12 21:17

When thinking about concurrent programs, we are sometimes blinded by the notion of bare threads. We create them, start them, join them, and sometimes even interrupt them, all by operating directly on those tiny little abstractions over several paths of simultaneous execution. At the same time we might be extremely reluctant to directly use synchronization primitives (semaphores, mutexes, etc.), preferring more convenient and tailored solutions – such as thread-safe containers. And this is great, because synchronization is probably the most difficult aspect of concurrent programming. Any place where we can avoid it is therefore one less place to be infested by nasty bugs it could ensue.

So why we still cling to somewhat low-level Threads for actual execution, while having no problems with specialized solutions for concurrent data exchange and synchronization?… Well, we can be simply unaware that “getting code to execute in parallel” is also something that can benefit from safety and clarity of more targeted approach. In Java, one such approach is oh-so-object-orientedly called executors.

As we might expect, an Executor is something that executes, i.e. runs, code. Pieces of those code are given it in a form of Runnables, just like it would happen for regular Threads:

  1. executor.execute(new Runnable() {
  2.     @Override public void run() {
  3.         calculatePiToDecimalPlaces(10000000);
  4.     }
  5. });

Executor itself is an abstract class, so it could be used without any knowledge about queuing policy, scheduling algorithms and any other details of the way it conducts execution of tasks. While this seems feasible in some real cases – such as servicing incoming network requests – executors are useful mainly because they are quite diverse in kind. Their complex and powerful variants are also relatively easy to use.

Let’s play in pool

Simple functions for creating different types of executors are contained within the auxiliary Executors class. Behind the scenes, most of them have a thread pool which they pull threads from when they are needed to process tasks. This pool may be of fixed or variable size, and can reuse a thread for more than one task,

Depending on how much load we expect and how many threads can we afford to create, the choice is usually between newCachedThreadPool and newFixedThreadPool. There is also peculiar (but useful) newSingleThreadExecutor, as well as time-based newScheduledThreadPool and newSingleThreadScheduledExecutor, allowing to specify delay for our Runnables by passing them to schedule method instead of execute.

Swapping them

There is one case where the abstract nature of base Executor class comes handy: testing and performance tuning. A certain types of executors can serve as good approximation of some common concurrency scenarios.

Suppose that we are normally handling our tasks using a pool with fixed number of threads, but we are not sure whether it’s actually the most optimal number. If our tasks appear to be mostly I/O-bound, it could be good idea to increase the thread count, seeing that threads waiting for I/O operations simply lay dormant for most of the time.
To see if our assumptions have grounds, and how big the increase can be, we can temporarily switch to cached thread pool. By experimenting with different levels of throughput and observing the average execution time along with numbers of threads used by application, we can get a sense of optimal number of threads for our fixed pool.
Similarly, we can adjust and possibly decrease this number for tasks that appear to be mostly CPU-bound.

Finally, it might be also sensible to use the single-threaded executor as a sort of “sanity check” for our complicated, parallel program. What we are checking this way is both correctness and performance, in rather simple and straightforward way.
For starters, our program should still compute correct results. Failing to do so serves as indication that seemingly correct behavior in multi-threaded setting may actually be an accidental side effect of unspotted hazards. In other words, threads might “align just right” if there is more than one running, and this would hide some insidious race conditions which we failed to account for.

As for performance, we should expect the single-thread code to run for longer time than its multi-thread variant. This is somewhat obvious observation that we might carelessly take for granted and thus never verify explicitly – and that’s a mistake. Indeed, it’s not unheard of to have parallelized algorithms which are actually slower than their serial counterparts. Throwing some threads is not a magic bullet, unfortunately: concurrency is still hard.

Tags: , , ,
Author: Xion, posted under Programming » 1 comment

About Java references

2011-12-17 19:22

There is somewhat common misconception about garbage collecting, that it totally frees the programmer from memory-related concerns. Granted, it makes the task easier in great many cases, but it does so at the expense of significant loss of control over objects’ lifetime. Normally, they are kept around for at least until they are not needed anymore – and usually that’s fine for the typical definitions of “need” and “at least”. Usually – but not always.

For those less typical use cases, garbage-collected environments provide mechanisms allowing to regain some of that lost control, to the extent necessary for particular task. Java, for example, offers a variety of different types of references, enabling to change the notion of what it means for an object to be eligible for garbage collecting. Choosing the right one for a problem at hand can be crucial, especially if we are concerned with the memory footprint of our application. Since – as the proverb goes – JVM expands to fill all available memory, it’s good to know about techniques which help maintain our heap size in check.

The default is strong

So today, I will discuss the SoftReference and WeakReference classes, which can be both found in the java.lang.ref package. They provide the so-called soft and weak references, which are both considerably less powerful when it comes to prolonging the lifetime of an object.

Tags: , , ,
Author: Xion, posted under Programming » 1 comment

Proste haszowanie obiektów

2011-10-15 19:37

W językach wspierających obiektowość zwykle mamy do czynienia z uniwersalną klasą bazową (Object), od której wszystkie inne muszą dziedziczyć. Składniki tej klasy są więc wspólne dla wszystkich obiektów. Czasami ma to negatywne skutki (vide wait i notify w Javie), ale zazwyczaj jest przydatne, bo wspólne składniki – takie jak toString – są często niezwykle użyteczne.
Istnieje jednak pewna metoda bazowa obiektów, której przeznaczenie nie musi być od razu oczywiste. Nazywa się ona dość podobnie w różnych językach: GetHashCode w C#, hashCode w Javie, zaś w Pythonie jest to po prostu __hash__. Nietrudno się więc domyślić, że ma ona coś wspólnego z hashem obiektu :) O co jednak dokładnie chodzi?

Hash to kompaktowa reprezentacja pewnej porcji danych, uzyskana za pomocą określonego algorytmu. Takim algorytmem może być na przykład MD5, SHA1, SHA256 i inne. Podstawowym wymaganiem, jakie stawia się takim funkcjom, jest determinizm: dla identycznych danych powinny one zwracać dokładnie te same wyniki.
Do czego jednak przydaje się możliwość haszowania< dowolnych obiektów? Otóż pozwala to na tworzenie kontenerów haszujących, takich jak zbiory i mapy. W Javie na przykład chodzi tu o pojemniki HashSet i HashMap, będące jednymi z możliwych implementacji ogólnych interfejsów Set i Map. Takie kontenery używają hashy jako podstawy swojego działania, zakładając, że ich porównywanie jest szybsze niż branie pod uwagę całych obiektów. Dopiero równość ich hashy pociąga za sobą konieczność porównania samych obiektów.

Być może nasuwa się tu od razu słuszny wniosek, że hashe dla obiektów potrzebne są wobec tego jedynie wtedy, gdy implementujemy własny sposób ich porównywania. (Opisywałem kiedyś, jak to się robi w języku C#). Często powinniśmy wtedy zapewnić taką implementację ekwiwalentu metody hashCode, która będzie spójna ze sposobem porównywania. Z grubsza chodzi o to, aby na hash wpływały pola, które bierzemy pod uwagę w metodzie equals/Equals/__eq__ – i tylko one.

W jaki sposób miałyby jednak to robić? No cóż, w teorii możemy zaprząc do pracy wymienione wyżej algorytmy i potraktować nimi połączone wartości pól obiektu (albo po prostu kawałek pamięci, w którym on rezyduje). W praktyce to bardzo kiepskie rozwiązanie (zwłaszcza wydajnościowo), bowiem wspomniane funkcje haszujące niezupełnie do tego służą. Istnieje bowiem różnica między kryptograficzną funkcją haszującą a zwykłą: ta pierwsza ma na celu przede wszystkim uniemożliwienie odtworzenia oryginalnych danych, jeśli znany jest tylko ich hash. W przypadku funkcji używanych wraz z pojemnikami haszującymi bardziej interesuje nas jednorodność, co (w uproszczeniu) oznacza, że hash obiektu powinien być wrażliwy na wartości poszczególnych pól tego obiektu. Z tego też powodu poniższe rozwiązanie:

  1. @Override
  2. public int hashCode() {
  3.     return 42;
  4. }

jest do niczego, mimo że świetnie spełnia teoretyczne wymaganie, aby dwa równe obiekty miały równe hashe.

Dostępna jest oczywiście wyrafinowana wiedza na temat konstruowania dobrych (a nawet doskonałych) funkcji haszujących, ale dokładnie rachunki prawdopodobieństwa kolizji nieczęsto nas interesują – zwłaszcza, jeśli właściwie nie wiemy, w jakich pojemnikach i wśród jakich innych obiektów skończą te nasze. Na szczęście mamy też prostsze warianty. Wśród nich interesująco wygląda na przykład sposób pokazany w znanej książce Effective Java, który wygląda mniej więcej w ten sposób:

  1. Zaczynamy od dowolnej liczby dodatniej.
  2. Dla każdego znaczącego pola w obiekcie:
    1. bierzemy jego 32-bitową reprezentację (w razie potrzeby używając operacji bitowej xor dla większych pól)
    2. dodajemy ją do wyniku, uprzednio pomnożonego przez małą liczbę pierwszą

Zastosowanie go np. do prostej klasy punktu 3D wyglądałoby na przykład tak:

  1. public class Point3D {
  2.     private float x, y, z;
  3.     // ...
  4.     @Override public int hashCode() {
  5.         int res = 23;
  6.         res = 31 * res + Float.floatToIntBits(x);
  7.         res = 31 * res + Float.floatToIntBits(y);
  8.         res = 31 * res + Float.floatToIntBits(z);
  9.         return res;
  10.     }
  11. }

Wybór 23 jest raczej arbitralny, natomiast 31 ma tę zaletę, że mnożenie przez nią liczby x jest równoważne przesunięciu bitowemu i odejmowaniu, tj. (x << 5) - x. Analogicznie jest zresztą dla innych liczb o jeden mniejszych od potęg dwójki.

Tags: , , ,
Author: Xion, posted under Programming » Comments Off on Proste haszowanie obiektów

Niekoniecznie długie nazwy

2011-10-09 23:22

Porzekadło głosi, że w informatyce są tylko dwa trudne problemy: nazewnictwo, mechanizmy cache‘owania i pomyłki o jedynkę. Jeśli chodzi o jeden dwa ostatnie, to może przyjrzymy się im przy innej okazji… Dzisiaj chciałbym za to zająć się pierwszym z nich: dobieraniem odpowiednich nazw dla konstrukcji programistycznych, takich jak funkcje czy klasy.

Nie każda nazwa jest właściwa. O tej trywialnej prawdzie każdy pewnie przekonał się już dawno, zwłaszcza jeśli przechodził przez fazę zmiennych a, b, c lub funkcji fun1 i fun2. Zdaje się zresztą, że kiedyś była to powszechna przypadłość, co widać zwłaszcza w przypadku starych API *niksowych. Najwyraźniej jednak poszliśmy kolektywnie po rozum do głowy i dziś już nikt nie nazwie funkcji wait3 czy wait4.

Nietrudno jest oczywiście wskazać podstawowy problem tego rodzaju nazw. Jakkolwiek jest on ściśle związany z długością, nie uzasadnia to automatycznie stwierdzenia, że wszystkie krótkie nazwy są złe. Żeby nie odchodzić daleko, wystarczy tylko spojrzeć na POSIX-owe, uniwersalne funkcje read i write. Ich nazwom nie brakuje dokładnie niczego; przeciwnie, próba dodania czegoś więcej wprowadzałaby tylko zamieszanie. readFromFileDescriptor może i wskazywałaby wyraźnie na źródło danych, ale czy zupełnie poprawne użycie takiej funkcji na uchwycie sieciowego gniazda (socket) nie byłoby mylące? O jakim pliku wtedy mówimy?
Naturalnie, w *niksach “wszystko jest plikiem” i należy o tym wiedzieć. Lecz skoro tak jest, to co zyskujemy przez dłuższą nazwę funkcji read? Niby z czego innego niż z pliku mielibyśmy czytać?…

Dywagując na ten temat muszę koniecznie zaznaczyć, że nazwy zaśmiecone oczywistymi informacjami nie są wcale hipotetycznym problemem. Moim ulubionym przykładem – ze względu na swoją groteskową wręcz ekstremalność – jest poniższe wywołanie:

  1. NSString* someString = @"Ala ma kota";
  2. NSString* otherString = [someString
  3.                          stringByReplacingOccurrencesOfString:@"kota"
  4.                          withString:@"psa"];

Ja wcale nie żartuję – tak w Objective-C (OSX/iOS) wygląda zastępowanie jednego ciągu w tekście innym. Zawsze chętnie wysłucham argumentów przekonujących o ekspresywności i opisowości podobnych nazw, ale nigdy nie uwierzę, że koderzy je rzeczywiście czytają. Zgaduję, że ich percepcja u statystycznego programisty polega na dostrzeżeniu “Repl” lewym okiem i “ccurr” prawym – albo coś w tym rodzaju. Jeśli mam rację, to nazwa ta jest znacząca w zaledwie 22 procentach; trudno to uznać za dobry stosunek sygnału do szumu.

Czy można było zrobić to lepiej? Zapewne – weźmy chociażby Javę:

  1. String someString = "Ala ma kota";
  2. String otherString = someString.replaceAll("kota", "psa");

Wygląda to całkiem dobrze. Okazuje się, że można użyć trzy razy krótszej nazwy i osiągnąć niemalże ten sam efekt, posługując się po prostu samą składnią języka (kolejnością parametrów i wartością zwracaną) zamiast długich tekstowych opisów.

Rozwlekłe nazwy – nawet jeśli camelCase czyni je znośnymi – nie zawsze są więc dobrą odpowiedzią. Czasami mogą one być równie nadmiarowe co niepotrzebne komentarze.

Tags: , , ,
Author: Xion, posted under Programming » 6 comments

Ujemna wartość bezwzględna?…

2011-09-13 22:31

Każdemu absolwentowi szkoły podstawowej (mam nadzieję, że wciąż podstawowej…) powinna być znana poniższa funkcja:

\displaystyle |x| =  \begin{cases}   x & \text{dla } x \ge 0 \\   -x & \text{dla } x < 0 \end{cases}

Tak, jest to zwyczajna wartość bezwzględna, znana również jako moduł liczby. Jej formalna definicja gwarantuje, że |x| \ge 0 dla każdego x \in \mathbb{R}. Innymi słowy, wartość bezwzględna nigdy nie może być ujemna. Nic więc dziwnego, że używamy jej chętnie w tych właśnie sytuacjach, gdy interesuje nas tylko dodatnia połowa osi liczb. Oto bardzo prosty przykład:

  1. private Random random = new Random();
  2. private int identifier = -1; // niezainicjowany
  4. private void generateIdentifier() {
  5.     identifier = Math.abs(random.nextInt());
  6. }
  8. public boolean isInitialized() {
  9.     return identifier >= 0;
  10. }

Mamy tu elementarną sztuczkę, polegającą na początkowym przypisaniu polu identifier wartości spoza zwykłej dziedziny (-1), co oznaczać ma brak identyfikatora. Możemy tak zrobić, bo dzięki wartości bezwzględnej (funkcji Math.abs) generowane losowe identyfikatory będą zawsze dodatnie.

Albo raczej prawie zawsze

Tags: , ,
Author: Xion, posted under Programming » 1 comment

© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with