#《亿级流量网站架构核心技术》目录一览 - TCP四层负载均衡 - 使用Hystrix实现隔离 - 基于Servlet3实现请求隔离 - 限流算法 令牌桶算法 漏桶算法 - 分布式限流 redis+lua实现 Nginx+Lua实现 - 使用sharding-jdbc分库分表 - Disruptor+Redis队列 简介 XML配置 EventWorker - Worker无状态化+任务化 - 数据量大时JIMDB同步不动 - 使用OpenResty开发高性能Web应用 - 单机闭环 分布式闭环 # 深入理解Java虚拟机：JVM高级特性与最佳实践（第2版） - HotSpot VM的热点代码探测能力可以通过执行计数器找出最具有编译价值的代码，然后通知JIT编译器以方法为单位进行编译。 - 被频繁调用，或方法中有效循环次数很多，将会分别触发标准编译和OSR（栈上替换）编译动作。 - 在2006年的JavaOne大会上，Sun公司宣布最终会把Java开源， - 所有的对象实例以及数组都要在堆上分配[1]， - 方法区（Method Area）与Java堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后 - 虽然Java虚拟机规范把方法区描述为堆的一个逻辑部分，但是它却有一个别名叫做Non-Heap（非堆），目的应该是与Java堆区分开来。 - 很多人都更愿意把方法区称为“永久代”（Permanent Generation），本质上两者并不等价，仅仅是因为HotSpot虚拟机的设计团队选择把GC分代收集扩展至方法区，或者说使用永久代来实现方法区而已， - 在目前已经发布的JDK 1.7的HotSpot中，已经把原本放在永久代的字符串常量池移出。 - 还可以选择不实现垃圾收集。相对而言，垃圾收集行为在这个区域是比较少出现的，但并非数据进入了方法区就如永久代的名字一样“永久”存在了。 - 根据Java虚拟机规范的规定，当方法区无法满足内存分配需求时，将抛出OutOfMemoryError异常。 - 运行时常量池（Runtime Constant Pool）是方法区的一部分。 - 常量池（Constant Pool Table），用于存放编译期生成的各种字面量和符号引用， - 运行期间也可能将新的常量放入池中，这种特性被开发人员利用得比较多的便是String类的intern（）方法。 - 在JDK 1.4中新加入了NIO（New Input/Output）类，引入了一种基于通道（Channel）与缓冲区（Buffer）的I/O方式，它可以使用Native函数库直接分配堆外内存，然后通过一个存储在Java堆中的DirectByteBuffer对象作为这块内存的引用进行操作。这样能在一些场景中显著提高性能，因为避免了在Java堆和Native - 虚拟机遇到一条new指令时，首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用，并且检查这个符号引用代表的类是否已被加载、解析和初始化过。如果没有，那必须先执行相应的类加载过程， - 那所分配内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”（Bump the Pointer）。如果Java堆中的内存并不是规整的，已使用的内存和空闲的内存相互交错，那就没有办法简单地进行指针碰撞了， - 那所分配内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”（Bump the Pointer）。如果Java堆中的内存并不是规整的，已使用的内存和空闲的内存相互交错，那就没有办法简单地进行指针碰撞了，虚拟机就必须维护一个列表，记录上哪些内存块是可用的，在分配的时候从列表中找到一块足够大的空间划分给对象实例，并更新列表上的记录，这种分配方式称为“空闲列表”（Free List）。选择哪种分配方式由Java堆是否规整决定，而Java堆是否规整又由所采用的垃圾收集器是否带有压缩整理功能决定。 - 那所分配内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”（Bump the Pointer）。如果Java堆中的内存并不是规整的，已使用的内存和空闲的内存相互交错，那就没有办法简单地进行指针碰撞了，虚拟机就必须维护一个列表，记录上哪些内存块是可用的，在分配的时候从列表中找到一块足够大的空间划分给对象实例，并更新列表上的记录，这种分配方式称为“空闲列表”（Free List）。选择哪种分配方式由Java堆是否规整决定，而Java堆是否规整又由所采用的垃圾收集器是否带有压缩整理功能决定。因此，在使用Serial、ParNew等带Compact过程的收集器时，系统采用的分配算法是指针碰撞，而使用CMS这种基于Mark-Sweep算法的收集器时，通常采用空闲列表。 - 解决这个问题有两种方案，一种是对分配内存空间的动作进行同步处理——实际上虚拟机采用CAS配上失败重试的方式保证更新操作的原子性；另一种是把内存分配的动作按照线程划分在不同的空间之中进行，即每个线程在Java堆中预先分配一小块内存，称为本地线程分配缓冲（Thread Local Allocation Buffer,TLAB）。 - 分配内存，就在哪个线程的TLAB上分配，只有TLAB用完并分配新的TLAB时，才需要同步锁定。虚拟机是否使用TLAB， - 虚拟机要对对象进行必要的设置，例如这个对象是哪个类的实例、如何才能找到类的元数据信息、对象的哈希码、对象的GC分代年龄等信息。这些信息存放在对象的对象头（Object Header）之中。 - 在HotSpot虚拟机中，对象在内存中存储的布局可以分为3块区域：对象头（Header）、实例数据（Instance Data）和对齐填充（Padding）。 - HotSpot虚拟机的对象头包括两部分信息，第一部分用于存储对象自身的运行时数据，如哈希码（HashCode）、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等，这部分数据的长度在32位和64位的虚拟机（未开启压缩指针）中分别为32bit和64bit，官方称它为“Mark Word”。 - 一个指向对象的引用，并没有定义这个引用应该通过何种方式去定位、访问堆中的对象的具体位置，所以对象访问方式也是取决于虚拟机实现而定的。目前主流的访问方式有使用句柄和直接指针两种。 - 如果使用句柄访问的话，那么Java堆中将会划分出一块内存来作为句柄池，reference中存储的就是对象的句柄地址，而句柄中包含了对象实例数据与类型数据各自的具体地址信息，如图2-2所示。 图　2-2　通过句柄访问对象 如果使用直接指针访问，那么Java堆对象的布局中就必须考虑如何放置访问类型数据的相关信息，而reference中存 - 这两种对象访问方式各有优势，使用句柄来访问的最大好处就是reference中存储的是稳定的句柄地址，在对象被移动（垃圾收集时移动对象是非常普遍的行为）时只会改变句柄中的实例数据指针，而reference本身不需要修改。 - 使用直接指针访问方式的最大好处就是速度更快，它节省了一次指针定位的时间开销，由于对象的访问在Java中非常频繁，因此这类开销积少成多后也是一项非常可观的执行成本。就 - 主要虚拟机Sun HotSpot而言，它是使用第二种方式进行对象访问的，但从整个软件开发的范围来看，各种语言和框架使用句柄来访问的情况也十分常见。 - Java堆用于存储对象实例，只要不断地创建对象，并且保证GC Roots到对象之间有可达路径来避免垃圾回收机制清除这些对象，那么在对象数量到达最大堆的容量限制后就会产生内存溢出异常。 - 将堆的最小值-Xms参数与最大值-Xmx参数设置为一样即可避免堆自动扩展）， - XX：+HeapDumpOnOutOfMemoryError可以让虚拟机在出现内 - public class HeapOOM{ static class OOMObject{ } public static void main（String[]args）{ List＜OOMObject＞list=new ArrayList＜OOMObject＞（）； while（true）{ list.add（new OOMObject（））； } } } - 要先分清楚到底是出现了内存泄漏（Memory Leak）还是内存溢出（Memory Overflow）。 - 由于在HotSpot虚拟机中并不区分虚拟机栈和本地方法栈， - 栈容量只由-Xss参数设定。 # Effective Java™ (Jason Arnold's Library) - Modules should be as small as possible but no smaller. - Code should be reused rather than copied. - The dependencies between modules should be kept to a minimum. - Errors should be detected as soon as possible after they are made, ideally at compile time. - like most other disciplines, consists of first learning the rules and then learning when to break them. - The language supports four kinds of types: interfaces (including annotations), classes (including enums), arrays, and primitives. The first three are known as reference types. Class instances and arrays are objects; primitive values are not. - the signature does not include the method's return type. - the descriptive term package-private instead of the technically correct term default access - One advantage of static factory methods is that, unlike constructors, they have names. - A second advantage of static factory methods is that, unlike constructors, they are not required to create a new object each time they're invoked. - This allows immutable classes (Item 15) to use preconstructed instances, or to cache instances as they're constructed, and dispense them repeatedly to avoid creating unnecessary duplicate objects. - the same object from repeated invocations allows classes to maintain strict control over what instances exist at any time. Classes that do this are said to be instance-controlled. There are several reasons to write instance-controlled classes. Instance control allows a class to guarantee that it is a singleton - 4). Also, it allows an immutable class (Item 15) to make the guarantee that no two equal instances exist: a.equals(b) if and only if a==b. If a class makes this guarantee, then its clients can use the == operator instead of the equals(Object) method, which may result in improved performance. Enum types (Item 30) provide this guarantee. - A third advantage of static factory methods is that, unlike constructors, they can return an object of any subtype of their return type. - One application of this flexibility is that an API can return objects without making their classes public. Hiding implementation classes in this fashion leads to a very compact API. This technique lends itself to interface-based frameworks (Item 18), where interfaces provide natural return types for static factory methods. - Nearly all of these implementations are exported via static factory methods in one noninstantiable class (java.util.Collections). The classes of the returned objects are all nonpublic. - Furthermore, using such a static factory method requires the client to refer to the returned object by its interface rather than its implementation class, which is generally good practice - java.util.EnumSet (Item 32), introduced in release 1.5, has no public constructors, only static factories. They return one of two implementations, depending on the size of the underlying enum type: if it has sixty-four or fewer elements, as most enum types do, the static factories return a RegularEnumSet instance, which is backed by a single long; if the enum type has sixty-five or more elements, the factories return a JumboEnumSet instance, backed by a long array. - Clients neither know nor care about the class of the object they get back from the factory; they care only that it is some subclass of EnumSet. - The class of the object returned by a static factory method need not even exist at the time the class containing the method is written. Such flexible static factory methods form the basis of service provider frameworks, such as the Java Database Connectivity API (JDBC). - There are three essential components of a service provider framework: a service interface, which providers implement; a provider registration API, which the system uses to register implementations, giving clients access to them; and a service access API, which clients use to obtain an instance of the service. - In the case of JDBC, Connection plays the part of the service interface, DriverManager.registerDriver is the provider registration API, DriverManager.getConnection is the service access API, and Driver is the service provider interface. - A fourth advantage of static factory methods is that they reduce the verbosity of creating parameterized type instances. - compiler can figure out the type parameters for you. This is known as type inference. - replace the wordy declaration above with this succinct alternative: - The main disadvantage of providing only static factory methods is that classes without public or protected constructors cannot be subclassed. - The same is true for nonpublic classes returned by public static factories. For example, it is impossible to subclass any of the convenience implementation classes in the Collections Framework. - as it encourages programmers to use composition instead of inheritance - A second disadvantage of static factory methods is that they are not readily distinguishable from other static methods. - Here are some common names for static factory methods: valueOf—Returns an instance that has, loosely speaking, the same value as its parameters. - of—A concise alternative to valueOf, popularized by EnumSet - getInstance—Returns an instance that is described by the parameters but cannot be said to have the same value. - newInstance—Like getInstance, except that newInstance guarantees that each instance returned is distinct from all others. - getType—Like getInstance, but used when the factory method is in a different class. Type indicates the type of object returned by the factory method. newType—Like newInstance, but used when the factory method is in a different class. Type indicates the type of object returned by the factory method. - In summary, static factory methods and public constructors both have their uses, and it pays to understand their relative merits. Often static factories are preferable, so avoid the reflex to provide public constructors without first considering static factories. - Consider a builder when faced with many constructor parameters - // Telescoping constructor pattern - does not scale well! - the telescoping constructor pattern works, but it is hard to write client code when there are many parameters, and harder still to read it. - Unfortunately, the JavaBeans pattern has serious disadvantages of its own. Because construction is split across multiple calls, a JavaBean may be in an inconsistent state partway through its construction. - the JavaBeans pattern precludes the possibility of making a class immutable - A well-designed module hides all of its implementation details, cleanly separating its API from its implementation. Modules then communicate only through their APIs and are oblivious to each others' inner workings. This concept, known as information hiding or encapsulation, is one of the fundamental tenets of software design - Information hiding is important for many reasons, most of which stem from the fact that it decouples the modules that comprise a system, allowing them to be developed, tested, optimized, used, understood, and modified in isolation. - This speeds up system development because modules can be developed in parallel. - eases the burden of maintenance because modules can be understood more quickly and debugged with little fear of harming other modules. - Information hiding increases software reuse because modules that aren't tightly coupled often prove useful in other contexts besides the ones - Finally, information hiding decreases the risk in building large systems, because individual modules may prove successful even if the system does not. - The rule of thumb is simple: make each class or member as inaccessible as possible. - If a top-level class or interface can be made package-private, it should be. - If you make it public, you are obligated to support it forever to maintain compatibility. - If a package-private top-level class (or interface) is used by only one class, consider making the top-level class a private nested class of the sole class that uses it (Item 22). - Also, a protected member of an exported class represents a public commitment to an implementation detail - There is one rule that restricts your ability to reduce the accessibility of methods. If a method overrides a superclass method, it is not permitted to have a lower access level in the subclass than it does in the superclass [JLS, 8.4.8.3]. - A special case of this rule is that if a class implements an interface, all of the class methods that are also present in the interface must be declared public. This is so because all members of an interface are implicitly public - Instance fields should never be public - so classes with public mutable fields are not thread-safe. - Even if a field is final and refers to an immutable object, by making the field public you give up the flexibility to switch to a new internal data representation in which the field does not exist. - It is critical that these fields contain either primitive values or references to immutable objects - Note that a nonzero-length array is always mutable, so it is wrong for a class to have a public static final array field, or an accessor that returns such a field. If a class has such a field or accessor, clients will be able to modify the contents of the array. This is a frequent source of security holes: - There are two ways to fix the problem. You can make the public array private and add a public immutable list: private static final Thing[] PRIVATE_VALUES = { ... }; public static final List VALUES =    Collections.unmodifiableList(Arrays.asList(PRIVATE_VALUES)); Alternatively, you can make the array private and add a public method that returns a copy of a private array: private static final Thing[] PRIVATE_VALUES = { ... }; public static final Thing[] values() { -     return PRIVATE_VALUES.clone(); } To choose between these alternatives, think about what the client is likely to do with the result. Which return type will be more convenient? - Item 14: In public classes, use accessor methods, not public fields - if a class is accessible outside its package, provide accessor methods, to preserve the flexibility to change the class's internal representation. - If a public class exposes its data fields, all hope of changing its representation is lost, as client code can be distributed far and wide. - However, if a class is package-private or is a private nested class, there is nothing inherently wrong with exposing its data fields—assuming they do an adequate job of describing the abstraction provided by the class. - clutter - If you use raw types, you lose all the safety and expressiveness benefits of generics. - dangerous. Since release 1.5, Java has provided a safe alternative known as unbounded wildcard types. - the unbounded wildcard type for the generic type Set is Set (read "set of some type"). It is the most general parameterized Set type, capable of holding any set. - Not to belabor the point, - both of which stem from the fact that generic type information is erased at runtime (Item 25). You must use raw types in class literals. - Because generic type information is erased at runtime, it is illegal to use the instanceof operator on parameterized types other than unbounded wildcard types. - Note that once you've determined that o is a Set, you must cast it to the wildcard type Set, not the raw type Set. This is a checked cast, so it will not cause a compiler warning. - In summary, using raw types can lead to exceptions at runtime, so don't use them in new code. They are provided only for compatibility and interoperability with legacy code that predates the introduction of generics. - Eliminate every unchecked warning that you can. - If you eliminate all warnings, you are assured that your code is typesafe, which is a very good thing. It means that you won't get a ClassCastException at runtime, and it increases your confidence that your program is behaving as you intended. - If you can't eliminate a warning, and you can prove that the code that provoked the warning is typesafe, then (and only then) suppress the warning with an @SuppressWarnings("unchecked") annotation. - If you suppress warnings without first proving that the code is typesafe, you are only giving yourself a false sense of security. - The code may compile without emitting any warnings, but it can still throw a ClassCastException at runtime. If, however, you ignore unchecked warnings that you know to be safe (instead of suppressing them), you won't notice when a new warning crops up that represents a real problem. - Always use the SuppressWarnings annotation on the smallest scope possible. - Never use SuppressWarnings on an entire class. Doing so could mask critical warnings. - Every time you use an @SuppressWarnings("unchecked") annotation, add a comment saying why it's safe to do so. This will help others understand the code, and more importantly, it will decrease the odds that someone will modify the code so as to make the computation unsafe. - Every unchecked warning represents the potential for a ClassCastException at runtime. - Avoid long parameter lists. Aim for four parameters or fewer. Most programmers can't remember longer parameter lists. - Long sequences of identically typed parameters are especially harmful. - increasing orthogonality. - power-to-weight - For parameter types, favor interfaces over classes - If there is an appropriate interface to define a parameter, use it in favor of a class that implements the interface. - For example, there is no reason ever to write a method that takes HashMap on input—use Map instead. - By using a class instead of an interface, you restrict your client to a particular implementation and force an unnecessary and potentially expensive copy operation if the input data happens to exist in some other form. - Prefer two-element enum types to boolean parameters. It makes your code easier to read and to write, especially if you're using an IDE that supports autocompletion. - judiciously - in release 1.5, the Arrays class was given a full complement of Arrays.toString methods (not varargs methods!) designed specifically to translate arrays of any type into strings. If you use Arrays.toString in place of Arrays.asList, the program produces the intended result: // The right way to print an array System.out.println(Arrays.toString(myArray)); - Now you know that you'll pay the cost of the array creation only in the 5 percent of all invocations where the number of parameters exceeds three. - The EnumSet class uses this technique for its static factories to reduce the cost of creating enum sets to a bare minimum. - judiciously # Java Concurrency in Practice - Not coincidentally, - Nor is it an encyclopedic reference for All Things Concurrency—for - bathrobe, - manifest - When threads share data, they must use synchronization mechanisms that can inhibit compiler optimizations, flush or invalidate memory caches, and create synchronization traffic on the shared memory bus. - contagious. - it rarely ends there; instead, it ripples through the application. - GUI applications are inherently asynchronous. - Writing thread-safe code is, at its core, about managing access to state, and in particular to shared, mutable state. - Whether an object needs to be thread-safe depends on whether it will be accessed from multiple threads. - believe—but it is always a good practice first to make your code right, and then make it fast. - At the heart of any reasonable definition of thread safety is the concept of correctness. - a class is thread-safe when it continues to behave correctly when accessed from multiple threads. - stateless objects are thread-safe. - The fact that most servlets can be implemented with no state greatly reduces the burden of making servlets thread-safe. - these built-in locks are called intrinsic locks or monitor locks. The lock is - however, this approach is fairly extreme, since it inhibits multiple clients from using the factoring servlet simultaneously - subvert - This attempt at a put-if-absent operation has a race condition, - This simple, coarse-grained approach restored safety, but at a high price. - unduly - There is frequently a tension between simplicity and performance. - resist the temptation to prematurely sacriflce simplicity (potentially compromising safety) for the sake of performance. - Together, they lay the foundation for building thread-safe classes and safely structuring - Visibility is subtle because the things that can go wrong are so counterintuitive. - reordering. There is no guarantee that operations in one thread will be performed in the order given by the program, as long as the reordering is not detectable from within that thread—even if the reordering is apparent to other threads. - downright - processor, and runtime can do some downright weird things to the order in - When food is stale, it is usually still edible—just less enjoyable. - When a thread reads a variable without synchronization, it may see a stale value, - nonvolatile long and double variables, the JVM is permitted to treat a 64-bit read or write as two separate 32-bit operations. - it is not safe to use shared mutable long and double variables in multithreaded programs unless they are declared volatile or guarded by a lock. - about mutual exclusion; it is also about memory visibility. To ensure that all threads see the most up-to-date values of shared mutable variables, the reading and writing threads must synchronize on a common lock. - Volatile variables are not cached in registers or in caches where they are hidden from other processors, so a read of a volatile variable always returns the most recent - making volatile variables a lighter-weight synchronization mechanism than synchronized. - volatile variable and subsequently thread B reads that same variable, the values of all variables that were visible to A prior to writing to the volatile variable become visible to B after reading the volatile variable. So from a memory visibility perspective, writing a volatile variable is like exiting a synchronized - However, we do not recommend relying too heavily on volatile variables for visibility; code that relies on volatile variables for visibility of arbitrary state is more fragile and harder to understand than code that uses locking. - Good uses of volatile variables include ensuring the visibility of their own state, that of the object they refer to, or indicating that an important lifecycle event (such as initialization or shutdown) has occurred. - anthropomorphized - The most common use for volatile variables is as a completion, interruption, or status flag, - Locking can guarantee both visibility and atomicity; - volatile variables can only guarantee visibility. - blatant - The most blatant form of publication is to - Publishing states in this way is problematic because any caller can modify its contents. In this case, the states array has escaped its intended scope, because what was supposed to be private state has been effectively made public. - This is a compelling reason to use encapsulation: - Do not allow the this reference to escape during construction. - When an object creates a thread from its constructor, it almost always shares its this reference with the new thread, either explicitly (by passing it to the constructor) or implicitly (because the Thread or Runnable is an inner class of the owning object). - There's nothing wrong with creating a thread in a constructor, but it is best not to start the thread immediately. - Instead, expose a start or initialize method that starts the owned thread. - Accessing shared, mutable data requires using synchronization; one way to avoid this requirement is to not share. - Swing uses thread confinement extensively. - Many concurrency errors in Swing applications stem from improper use of these confined objects from - Single-threaded subsystems can sometimes offer a simplicity benefit that outweighs the fragility of ad-hoc thread confinement. - are confining the modification to a single thread to prevent race conditions, and the visibility guarantees for volatile variables ensure that other threads see the most up-to-date value. - There is no way to obtain a reference to a primitive variable, so the language semantics ensure that primitive local variables are always stack confined. - In loadTheArk, we instantiate a TreeSet and store a reference to it in animals. At this point, there is exactly one reference to the Set, held in a local variable and therefore confined to the executing thread. However, if we were - maintaining thread confinement is ThreadLocal, which allows you to associate a per-thread value with a value-holding object. - When a thread calls ThreadLocal.get for the first time, initialValue is consulted to provide the initial value for that thread. Conceptually, you can think of a - The thread-specific values are stored in the Thread object itself; when the thread terminates, the thread-specific values can be garbage collected. - If you are porting a single-threaded application to a multithreaded environment, you can preserve thread safety by converting shared global variables into ThreadLocals, if the semantics of the shared globals permits this; - Immutable objects are always thread-safe. - subverted - An object whose fields are all final may still be mutable, since final fields can hold references to mutable objects. - An object is immutable if: Its state cannot be modifled after construction; All its flelds are final;[12] and It is properly constructed (the this reference does not escape during construction). - There is a difference between an object being immutable and the reference to it being immutable. - It is the use of final fields that makes possible the guarantee of initialization safety - Just as it is a good practice to make all fields private unless they need greater - it is a good practice to make all fields final unless they need to be mutable. - Immutable objects can be used safely by any thread without additional synchronization, even when synchronization is not used to publish them. - final fields can be safely accessed without additional synchronization. However, if final fields refer to mutable objects, synchronization is still required to access the state of the objects they refer to. - Objects that are not immutable must be safely published, which usually entails synchronization by both the publishing and the consuming thread. - To publish an object safely, both the reference to the object and the object's state must be made visible to other threads at the same time. - constitute - Using a static initializer is often the easiest and safest way to publish objects that - public static Holder holder = new Holder(42); Static initializers are executed by the JVM at class initialization time; because of internal synchronization in the JVM, this mechanism is - Objects that are not technically immutable, but whose state will not be modified after publication, are called effectively immutable. - The publication requirements for an object depend on its mutability: Immutable objects can be published through any mechanism; Effectively immutable objects must be safely published; Mutable objects must be safely published, and must be either threadsafe or guarded by a lock. - Operations with state-based preconditions are called state-dependent - Blocking library classes such as BlockingQueue, Semaphore, and other synchronizers are covered in Chapter 5; creating state-dependent classes using the low-level mechanisms provided by the platform and class library is covered in Chapter 14. - Ownership is not embodied explicitly in the language, - Ownership implies control, but once you publish a reference to a mutable object, you no longer have exclusive control; at best, you might have "shared ownership". - Collection classes often exhibit a form of "split ownership", in which the collection owns the state of the collection infrastructure, but client code owns the objects stored in the collection. - they should either be thread-safe, effectively immutable, or explicitly guarded by a lock. - You can ensure that it is only accessed from a single thread (thread confinement), or that all access to it is properly guarded by a lock. - Instance confinement is one of the easiest ways to build thread-safe classes. - The Java monitor pattern is used by many library classes, such as Vector and Hashtable. - The primary advantage of the Java monitor pattern is its simplicity. - Clients that improperly acquire another object's lock could cause liveness problems, and verifying that a publicly accessible lock is properly used requires examining the entire program rather than a single class. - Immutable values can be freely shared and published, so we no longer need to copy the locations when returning them. - Because the underlying state variables lower and upper are not independent, NumberRange cannot simply delegate thread safety to its thread-safe state variables. - a variable is suitable for being declared volatile only if it does not participate in invariants involving other state variables. - If we provided separate getters for x and y, then the values could change between the time one coordinate is retrieved and the other, resulting in a caller seeing an inconsistent value: an (x, y) location where the - PublishingVehicleTracker derives its thread safety from delegation to an underlying ConcurrentHashMap, but this time the contents of the Map are thread-safe mutable points rather than immutable ones. - To make this approach work, we have to use the same lock that the List uses by using client-side locking or external locking. -        public List list =              Collections.synchronizedList(new ArrayList());       ...       public boolean putIfAbsent(E x) {              synchronized (list)  {                     boolean absent = !list.contains(x); - (Like Collections.synchronizedList and other collections wrappers, ImprovedList assumes that once a list is passed to its constructor, the client will not use the underlying list directly again, accessing it only through the ImprovedList.) - ImprovedList adds an additional level of locking using its own intrinsic lock. It does not care whether the underlying List is thread-safe, because it provides its own consistent locking that provides thread safety even if the List is not - Each use of synchronized, volatile, or any thread-safe class reflects a synchronization policy defining a strategy for ensuring the integrity of data in the face of concurrent access. - delegation is one of the most effective strategies for creating thread-safe classes: just let existing thread-safe classes manage all the state. - Collections.synchronizedXxx factory methods. These classes achieve thread safety by encapsulating their state and synchronizing every public method so that only one thread at a time can access the collection state. - using iterators does not obviate the need to lock the collection during iteration if other threads can concurrently modify it. - The iterators returned by the synchronized collections are not designed to deal with concurrent modification, and they are fail-fast—meaning that if they detect that the collection has changed since iteration began, they throw the unchecked ConcurrentModificationException. - These fail-fast iterators are not designed to be foolproof—they are designed to catch concurrency errors on a "good-faith-effort" basis and thus act only as early-warning indicators for concurrency problems. They are implemented by associating a modification count with the collection: if the modification count changes during iteration, hasNext or next throws ConcurrentModificationException. However, this check is done without synchronization, so there is a risk of seeing a stale - An alternative to locking the collection during iteration is to clone the collection and iterate the copy instead. - Since the clone is thread-confined, no other thread can modify it during iteration, eliminating the possibility of ConcurrentModificationException. - Similarly, the containsAll, removeAll, and retainAll methods, as well as the constructors that take collections as arguments, also iterate the collection. All of these indirect uses of iteration can cause ConcurrentModificationException. - CopyOnWriteArrayList, a replacement for synchronized List implementations for cases where traversal is the dominant operation. - Queue operations do not block; if the queue is empty, the retrieval operation returns null. While you can simulate the behavior of a Queue with a List—in fact, LinkedList also implements Queue—the Queue classes were added because eliminating the random-access requirements of List admits more efficient concurrent implementations. - Java 6 adds ConcurrentSkipListMap and ConcurrentSkipListSet, which are concurrent replacements for a synchronized SortedMap or SortedSet (such as TreeMap or TreeSet wrapped with synchronizedMap). - if hashCode does not spread out hash values well, elements may be unevenly distributed among buckets; - it uses a finer-grained locking mechanism called lock striping (see Section 11.4.3) to allow a greater degree of shared access. - with little performance penalty for single-threaded access. - ConcurrentHashMap, along with the other concurrent collections, further improve on the synchronized collection classes by providing iterators that do not throw ConcurrentModificationException, thus eliminating the need to lock the collection during iteration. - The iterators returned by ConcurrentHashMap are weakly consistent instead of fail-fast. - A weakly consistent iterator can tolerate concurrent modification, traverses elements as they existed when the iterator was constructed, and may (but is not guaranteed to) reflect modifications to the collection after the construction of the iterator. - As with all improvements, there are still a few tradeoffs. The semantics of methods that operate on the entire Map, such as size and isEmpty, have been slightly weakened to reflect the concurrent nature of the collection. Since the result of size could be out of date by the time it is computed, it is really only an estimate, so size is allowed to return an approximation instead of an exact count. - While at first this may seem disturbing, in reality methods like size and isEmpty are far less useful in concurrent environments because these quantities are moving targets. - So the requirements for these operations were weakened to enable performance optimizations for the most important operations, primarily get, put, containsKey, and remove. - The one feature offered by the synchronized Map implementations but not by ConcurrentHashMap is the ability to lock the map for exclusive access. - this is a reasonable tradeoff: concurrent collections should be expected to change their contents continuously. - ConcurrentHashMap not an appropriate drop-in replacement. - Since a ConcurrentHashMap cannot be locked for exclusive access, we cannot use client-side locking to create new atomic operations such as put-if-absent, - common compound operations such as put-if-absent, remove-if-equal, and replace-if-equal are implemented as atomic operations and specified by the ConcurrentMap interface, - CopyOnWriteArraySet is a concurrent replacement for a synchronized Set.) - They implement mutability by creating and republishing a new copy of the collection every time it is modified. - Iterators for the copy-on-write collections retain a reference to the backing array that was current at the start of iteration, and since this will never change, they need to synchronize only briefly to ensure visibility of the array contents. - iterators returned by the copy-on-write collections do not throw ConcurrentModificationException and return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications. - the copy-on-write collections are reasonable to use only when iteration is far more common than modification. - Queues can be bounded or unbounded; unbounded queues are never full, so a put on an unbounded queue never blocks. - The producerconsumer pattern simplifies development because it removes code dependencies between producer and consumer classes, and simplifies workload management by decoupling activities that may produce or consume data at different or variable rates. - Producers don't need to know anything about the identity or number of consumers, or even whether they are the only producer—all they have to do is place data items on the queue. - one person washes the dishes and places them in the dish rack, and the other person retrieves the dishes from the rack and dries them. In this scenario, the dish rack acts as a blocking queue; if there are no dishes in the rack, the consumer waits until there are dishes to dry, and if the rack fills up, the producer has to stop washing until there is more space. - Blocking queues also provide an offer method, which returns a failure status if the item cannot be enqueued. This enables you to create more flexible policies for dealing with overload, such as shedding load, serializing excess work items and writing them to disk, reducing the number of producer threads, or throttling producers in some other manner. - Bounded queues are a powerful resource management tool for building reliable applications: they make your program more robust to overload by throttling activities that threaten to produce more work than can be handled. - LinkedBlockingQueue and ArrayBlockingQueue are FIFO queues, analogous to LinkedList and ArrayList but with better concurrent performance than a synchronized List. - PriorityBlockingQueue is a priority-ordered queue, which is useful when you want to process elements in an order other than FIFO. Just like other sorted collections, PriorityBlockingQueue can compare elements according to their natural order (if they implement Comparable) or using a Comparator. - The last BlockingQueue implementation, SynchronousQueue, is not really a queue at all, in that it maintains no storage space for queued elements. Instead, it maintains a list of queued threads waiting to enqueue or dequeue an element. - While this may seem a strange way to implement a queue, it reduces the latency associated with moving data from producer to consumer because the work can be handed off directly. (In a traditional queue, the enqueue and dequeue operations must complete sequentially before a unit of work can be handed off.) The direct handoff also feeds back more information about the state of the task to the producer; when the handoff is accepted, it knows a consumer has taken responsibility for it, rather than simply letting it sit on a queue somewhere—much like the difference between handing a document to a colleague and merely putting it in her mailbox and hoping she gets it soon. - Since a SynchronousQueue has no storage capacity, put and take will block unless another thread is already waiting to participate in the handoff. - Synchronous queues are generally suitable only when there are enough consumers that there nearly always will be one ready to take the handoff. - Executor task execution framework, which itself uses the producer-consumer pattern. - For mutable objects, producer-consumer designs and blocking queues facilitate serial thread confinement for handing off ownership of objects from producers to consumers. - thread-confined object is owned exclusively by a single thread, but that ownership can be "transferred" by publishing it safely where only one other thread will gain access to it and ensuring that the publishing thread does not access it after the handoff. - Object pools exploit serial thread confinement, "lending" an object to a requesting thread. As long as the pool contains sufficient internal synchronization to publish the pooled object safely, and as long as the clients do not themselves publish the pooled object or use it after returning it to the pool, ownership can be transferred safely from thread to thread. - it could also done with the atomic remove method of ConcurrentMap or the compareAndSet method of AtomicReference. - Deque (pronounced "deck") and BlockingDeque, that extend Queue and BlockingQueue. - deques lend themselves to a related pattern called work stealing. - A producerconsumer design has one shared work queue for all consumers; in a work stealing design, every consumer has its own deque. If a consumer exhausts the work in its own deque, it can steal work from the tail of someone else's deque. - Work stealing can be more scalable than a traditional producer-consumer design because workers don't contend for a shared work queue; most of the time they access only their own deque, reducing contention. - When a worker has to access another's queue, it does so from the tail rather than the head, further reducing contention. - Work stealing is well suited to problems in which consumers are also producers—when performing a unit of work is likely to result in the identification of more work. For example, processing a page in a web crawler usually results in the identification of new pages to be crawled. - when its deque is empty, it looks for work at the end of someone else's deque, ensuring that each worker stays busy. - When a method can throw InterruptedException, it is telling you that it is a blocking method, and further that if it is interrupted, it will make an effort to stop blocking early. - Interruption is a cooperative mechanism. One thread cannot force another to stop what it is doing and do something else; when thread A interrupts thread B, A is merely requesting that B stop what it is doing when it gets to a convenient stopping point—if it feels like it. - When your code calls a method that throws InterruptedException, then your method is a blocking method too, and must have a plan for responding to interruption. - Blocking queues are unique among the collections classes: not only do they act as containers for objects, but they can also coordinate the control flow of producer and consumer threads because take and put block until the queue enters the desired state (not empty or not full). - A synchronizer is any object that coordinates the control flow of threads based on its state. Blocking queues can act as synchronizers; other types of synchronizers include semaphores, barriers, and latches. - All synchronizers share certain structural properties: they encapsulate state that determines whether threads arriving at the synchronizer should be allowed to pass or forced to wait, provide methods to manipulate that state, and provide methods to wait efficiently for the synchronizer to enter the desired state. - Latches can be used to ensure that certain activities do not proceed until other one-time activities complete, such as: - Ensuring that a computation does not proceed until resources it needs have been initialized. - A simple binary (two-state) latch could be used to indicate "Resource R has been initialized", and any activity that requires R would wait first on this latch. - Waiting until all the parties involved in an activity, for instance the players in a multi-player game, are ready to proceed. In this case, the latch reaches the terminal state after all the players are ready. - Using a starting gate allows the master thread to release all the worker threads at once, and the ending gate allows the master thread to wait for the last thread to finish rather than waiting sequentially for each thread to finish. - FutureTask also acts like a latch. (FutureTask implements Future, which describes an abstract result-bearing computation - a FutureTask is implemented with a Callable, the result-bearing equivalent of Runnable, and can be in one of three states: waiting to run, running, or completed. - subsumes - Once a FutureTask enters the completed state, it stays in that state forever. - FutureTask conveys the result from the thread executing the computation to the thread(s) retrieving the result; the specification of FutureTask guarantees that this transfer constitutes a safe publication of the result. -             startGate.await();                                          try {                                                 task.run();                                          } finally {                                                 endGate.countDown(); -                      t.start();              }              long start = System.nanoTime();              startGate.countDown();              endGate.await();              long end = System.nanoTime();              return end-start; - FutureTask is used by the Executor framework to represent asynchronous tasks, and can also be used to represent any potentially lengthy computation that can be started before the results are needed. - Counting semaphores are used to control the number of activities that can access a certain resource or perform a given action at the same time - semaphores can be used to implement resource pools or to impose a bound on a collection. - (An easier way to construct a blocking object pool would be to use a BlockingQueue to hold the pooled resources.) - Similarly, you can use a Semaphore to turn any collection into a blocking bounded collection, as illustrated by BoundedHashSet in Listing 5.14. - The key difference is that with a barrier, all the threads must come together at a barrier point at the same time in order to proceed. Latches are for waiting for events; barriers are for waiting for other threads. - rendezvous - CyclicBarrier allows a fixed number of parties to rendezvous repeatedly at a barrier point and is useful in parallel iterative algorithms that break down a problem into a fixed number of independent subproblems. - Threads call await when they reach the barrier point, and await blocks until all the threads have reached the barrier point. If all threads meet at the barrier point, the barrier has been successfully passed, in which case all threads are released and the barrier is reset so it can be used again. - If a call to await times out or a thread blocked in await is interrupted, then the barrier is considered broken and all outstanding calls to await terminate with BrokenBarrierException. - If the barrier is successfully passed, await returns a unique arrival index for each thread, which can be used to "elect" a leader that takes some special action in the next iteration. - Using Semaphore to Bound a Collection. - Barriers are often used in simulations, where the work to calculate one step can be done in parallel but all the work associated with a given step must complete before advancing to the next step. - Another form of barrier is Exchanger, a two-party barrier in which the parties exchange data at the barrier point [CPJ 3.4.3]. Exchangers are useful when the parties perform asymmetric activities, for example when one thread fills a buffer with data and the other thread consumes the data from the buffer; these threads could use an Exchanger to meet and exchange a full buffer for an empty one. When two threads exchange objects via an Exchanger, the exchange constitutes a safe publication of both objects to the other party. - Nearly every server application uses some form of caching. Reusing the results of a previous computation can reduce latency and increase throughput, at the cost of some additional memory usage. -               int count = Runtime.getRuntime().availableProcessors(); -               this.mainBoard = board;              int count = Runtime.getRuntime().availableProcessors();              this.barrier = new CyclicBarrier(count,                            new Runnable() {                                   public void run() {                                          mainBoard.commitNewValues(); - A naive cache implementation is likely to turn a performance bottleneck into a scalability bottleneck, even if it does improve single-threaded performance. - We've already seen a class that does almost exactly this: FutureTask. FutureTask represents a computational process that may or may not already have completed. FutureTask.get returns the result of the computation immediately if it is available; otherwise it blocks until the result has been computed and then returns it. - This window is far smaller than in Memoizer2, but because the if block in compute is still a nonatomic check-thenact sequence, it is possible for two threads to call compute with the same value at roughly the same time, both see that the cache does not contain the desired value, and both start the computation. - Figure 5.4. Unlucky Timing that could Cause Memoizer3 to Calculate the Same Value Twice. - Memoizer3 is vulnerable to this problem because a compound action (put-if-absent) is performed on the backing map that cannot be made atomic using locking. - Memoizer in Listing 5.19 takes advantage of the atomic putIfAbsent method of ConcurrentMap, closing the window of vulnerability in Memoizer3. - Caching a Future instead of a value creates the possibility of cache pollution: if a computation is cancelled or fails, future attempts to compute the result will also indicate cancellation or failure. To avoid this, Memoizer removes the Future from the cache if it detects that the computation was cancelled; it might also be desirable to remove the Future upon detecting a RuntimeException if the computation might succeed on a future attempt. - Memoizer also does not address cache expiration, but this could be accomplished by using a subclass of FutureTask that associates an expiration time with each result and periodically scanning the cache for expired entries. - It's the mutable state, stupid.[1]All concurrency issues boil down to coordinating access to mutable state. The less mutable state, the easier it is to ensure thread safety. - Make fields final unless they need to be mutable. - Immutable objects are automatically thread-safe.Immutable objects simplify concurrent programming tremendously. They are simpler and safer, and can be shared freely without locking or defensive copying. - Encapsulating data within objects makes it easier to preserve their invariants; encapsulating synchronization within objects makes it easier to comply with their synchronization policy. - Guard each mutable variable with a lock. - Guard all variables in an invariant with the same lock. - Hold locks for the duration of compound actions. - A program that accesses a mutable variable from multiple threads without synchronization is a broken program. Don't rely on clever - Include thread safety in the design process—or explicitly document that your class is not thread-safe. - Document your synchronization policy. - Ideally, tasks are independent activities: work that doesn't depend on the state, result, or side effects of other tasks. - Independence facilitates concurrency, as independent tasks can be executed in parallel if there are adequate processing resources. - Server applications should exhibit both good throughput and good responsiveness under normal load. - Further, applications should exhibit graceful degradation as they become overloaded, rather than simply falling over under heavy load. - Choosing good task boundaries, coupled with a sensible task execution policy (see Section 6.2.2), can help achieve these goals. - Thread lifecycle overhead. Thread creation and teardown are not free. - Resource consumption. Active threads consume system resources, especially memory. - of memory, putting pressure on the garbage collector, and having many threads competing for the CPUs can impose other performance costs as well. - the sequential approach suffers from poor responsiveness and throughput, and the thread-per-task approach suffers from poor resource management. - The primary abstraction for task execution in the Java class libraries is not Thread, but Executor, - Executor is based on the producer-consumer pattern, where activities that submit tasks are the producers (producing units of work to be done) and the threads that execute tasks are the consumers (consuming those units of work). - Using an Executor is usually the easiest path to implementing a producer-consumer design in your application. - strewn - task submission code tends to be strewn throughout the program and harder to expose. -      private static final Executor exec           = Executors.newFixedThreadPool(NTHREADS); - The value of decoupling submission from execution is that it lets you easily specify, and subsequently change without great difficulty, the execution policy for a given class of tasks. An execution policy specifies the "what, where, when, and how" of task execution, including: - Separating the specification of execution policy from task submission makes it practical to select an execution policy at deployment time that is matched to the available hardware. - Whenever you see code of the form: new Thread(runnable).start() and you think you might at some point want a more flexible execution policy, seriously consider replacing it with the use of an Executor. - A thread pool, as its name suggests, manages a homogeneous pool of worker threads. - newCachedThreadPool. A cached thread pool has more flexibility to reap idle threads when the current size of the pool exceeds the demand for processing, and to add new threads when demand increases, but places no bounds on the size of the pool. - newSingleThreadExecutor. A single-threaded executor creates a single worker thread to process tasks, replacing it if it dies unexpectedly. Tasks are guaranteed to be processed sequentially according to the order imposed by the task queue (FIFO, LIFO, priority order). - newScheduledThreadPool. A fixed-size thread pool that supports delayed and periodic task execution, similar to Timer. - Switching from a thread-per-task policy to a pool-based policy has a big effect on application stability: the web server will no longer fail under heavy load.[5] It also degrades more gracefully, since it does not create thousands of threads that compete for limited CPU and memory resources. - And using an Executor opens the door to all sorts of additional opportunities for tuning, management, monitoring, logging, error reporting, and other possibilities that would have been far more difficult to add without a task execution framework. - shut down an Executor could prevent the JVM from exiting. - The lifecycle implied by ExecutorService has three states—running, shutting down, and terminated. - The Timer facility manages the execution of deferred ("run this task in 100 ms") and periodic ("run this task every 10 ms") tasks. - However, Timer has some drawbacks, and ScheduledThreadPoolExecutor should be thought of as its replacement.[6] You can construct a ScheduledThreadPoolExecutor through its constructor or through the newScheduledThreadPool factory. - Another problem with Timer is that it behaves poorly if a TimerTask throws an unchecked exception. The Timer thread doesn't catch the exception, so an unchecked exception thrown from a TimerTask terminates the timer thread. - In this case, TimerTasks that are already scheduled but not yet executed are never run, and new tasks cannot be scheduled. (This problem, called "thread leakage" is described in Section 7.3, along with techniques for avoiding it.) - ScheduledThreadPoolExecutor deals properly with ill-behaved tasks; there is little reason to use Timer in Java 5.0 or later. - own scheduling service, you may still be able to take advantage of the library by using a DelayQueue, a BlockingQueue implementation that provides the scheduling functionality of ScheduledThreadPoolExecutor. A DelayQueue manages a collection of Delayed objects. A Delayed has a delay time associated with it: DelayQueue lets you take an element only if its delay has expired. -              timer.schedule(new ThrowTask(), 1);            SECONDS.sleep(1);           timer.schedule(new ThrowTask(), 1);           SECONDS.sleep(5);    }     static class ThrowTask extends TimerTask {          public void run() { throw new RuntimeException(); }    } - Tasks are usually finite: they have a clear starting point and they eventually terminate. The lifecycle of a task executed by an Executor has four phases: created, submitted, started, and completed. - It returns immediately or throws an Exception if the task has already completed, but if not it blocks until the task completes. If the task completes by throwing an exception, get rethrows it wrapped in an ExecutionException; if it was cancelled, get throws CancellationException. - a Future, so that you can submit a Runnable or a Callable to an executor and get back a Future that can be used to retrieve the result or cancel the task. You can also explicitly instantiate a FutureTask for a given Runnable or Callable. (Because FutureTask implements Runnable, it can be submitted to an Executor for execution or executed directly by calling its run method.) - (Because one task is largely CPU-bound and the other is largely I/O-bound, this approach may yield improvements even on single-CPU systems.) - Heterogeneous - finer-grained parallelism among similar tasks, this approach will yield diminishing returns. - ExecutorCompletionService is quite straightforward. The constructor creates a BlockingQueue to hold the completed results. Future-Task has a done method that is called when the computation completes. When a task is submitted, it is wrapped with a QueueingFuture, a subclass of FutureTask that overrides done to place the result on the BlockingQueue, as shown in Listing 6.14. The take and poll methods delegate to the BlockingQueue, blocking if results are not yet available. - private class QueueingFuture extends FutureTask {      QueueingFuture(Callable c) { super(c); }      QueueingFuture(Runnable t, V r) { super(t, r); }      protected void done() {            completionQueue.add(this);    }} -             CompletionService completionService =                new ExecutorCompletionService(executor);           for (final ImageInfo imageInfo : info)                completionService.submit(new Callable() {                   public ImageData call() {                         return imageInfo.downloadImage();                 }            }); -       long endNanos = System.nanoTime() + TIME_BUDGET; -          // Only wait for the remaining time budget          long timeLeft = endNanos - System.nanoTime();          ad = f.get(timeLeft, NANOSECONDS); -     }   catch (TimeoutException e) {          ad = DEFAULT_AD;          f.cancel(true);    }      page.setAd(ad);      return page;} - The invokeAll method takes a collection of tasks and returns a collection of Futures. The two collections have identical structures; invokeAll adds the Futures to the returned collection in the order imposed by the task collection's iterator, thus allowing the caller to associate a Future with the Callable it represents. - The Executor framework permits you to decouple task submission from execution policy and supports a rich variety of execution policies; whenever you find yourself creating threads to perform tasks, consider using an Executor instead. - preemptively - There are only cooperative mechanisms, by which the task and the code requesting cancellation follow an agreed-upon protocol. - A task that wants to be cancellable must have a cancellation policy that specifies the "how", "when", and "what" of cancellation—how other code can request cancellation, when the task checks whether cancellation has been requested, and what actions the task takes in response to a cancellation request. - Using a Volatile Field to Hold Cancellation State. -      public void cancel() { cancelled = true;  }     public synchronized List get() {         return new ArrayList(primes);     } -     try {        SECONDS.sleep(1);    } finally { - certain blocking library methods support interruption. Thread interruption is a cooperative mechanism for a thread to signal another thread that it should, at its convenience and if it feels like it, stop what it is doing and do something else. - There is nothing in the API or language specification that ties interruption to any specific cancellation semantics, but in practice, using interruption for anything but cancellation is fragile and difficult to sustain in larger applications. - Each thread has a boolean interrupted status; interrupting a thread sets its interrupted status to true. - The JVM makes no guarantees on how quickly a blocking method will detect interruption, but in practice this happens reasonably quickly. - Calling interrupt does not necessarily stop the target thread from doing what it is doing; it merely delivers the message that interruption has been requested. - Interruption is usually the most sensible way to implement cancellation. - A thread should be interrupted only by its owner; the owner can encapsulate knowledge of the thread's interruption policy in an appropriate cancellation mechanism such as a shutdown method. - Because each thread has its own interruption policy, you should not interrupt a thread unless you know what interruption means to that thread. - Critics have derided the Java interruption facility because it does not provide a preemptive interruption capability and yet forces developers to handle InterruptedException. - What you should not do is swallow the InterruptedException by catching it and doing nothing in the catch block, unless your code is actually implementing the interruption policy for a thread. - Only code that implements a thread's interruption policy may swallow an interruption request. General-purpose task and library code should never swallow interruption requests. -               try {                  return queue.take();              } catch (InterruptedException e) {                  interrupted = true;                  // fall through and retry              }          }      } finally {          if (interrupted)              Thread.currentThread().interrupt();      }} For example, when a worker thread owned by a ThreadPoolExecutor detects interruption, it checks whether the pool is being shut down. If so, it performs some pool cleanup before terminating; otherwise it may create a new thread to restore the thread pool to the desired size. - This is an appealingly simple approach, but it violates the rules: you should know a thread's interruption policy before interrupting it. - Undesirable memory retention can be easily tested with heap-inspection tools that measure application memory usage; - AtomicInteger();  private final ThreadFactory factory      = Executors.defaultThreadFactory();  public Thread newThread(Runnable r) {    numCreated.incrementAndGet();    return factory.newThread(r); - Listing 12.9. Test Method to Verify Thread Pool Expansion. public void testPoolExpansion() throws InterruptedException {  int MAX_SIZE = 10;  ExecutorService exec = Executors.newFixedThreadPool(MAX_SIZE);  for (int i = 0; i < 10* MAX_SIZE; i++)    exec.execute(new Runnable() {      public void run() {        try {          Thread.sleep(Long.MAX_VALUE); - 12.1.6. Generating More Interleavings Since many of the potential failures in concurrent code are low-probability events, testing for concurrency errors is a numbers game, but there are some things you can do to improve your chances. - We've already mentioned how running on multiprocessor systems with fewer processors than active threads can generate more interleavings than either a single-processor system or one with many processors. - A useful trick for increasing the number of interleavings, and therefore more effectively exploring the state space of your programs, is to use Thread.yield to encourage more context switches during operations that access shared state. - (The effectiveness of this technique is platform-specific, since the JVM is free to treat Thread.yield as a no-op - Listing 12.10. Using Thread.yield to Generate More Interleavings. public synchronized void transferCredits(Account from,                     Account to,                     int amount) {  from.setBalance(from.getBalance() - amount);  if (random.nextInt(1000) > THRESHOLD)    Thread.yield();  to.setBalance(to.getBalance() + amount);} - Performance tests are often extended versions of functionality tests. - This test suggests that LinkedBlockingQueue scales better than ArrayBlockingQueue. This may seem odd at first: a linked queue must allocate a link node object for each insertion, and hence seems to be doing more work than the array-based queue. However, even though it has more allocation and GC overhead, a linked queue allows more concurrent access by puts and takes than an array-based queue because the best linked queue algorithms allow the head and tail to be updated independently. - Because allocation is usually threadlocal, algorithms that can reduce contention by doing more allocation usually scale better. - So, unless threads are continually blocking anyway because of tight synchronization requirements, nonfair semaphores provide much better throughput and fair semaphores provides lower variance. Because the results are so dramatically different, Semaphore forces its clients to decide which of the two factors to optimize for. - On HotSpot, running your program with -XX:+PrintCompilation prints out a message when dynamic compilation runs, so you can verify that this is prior to, rather than during, measured test runs. - On the other hand, if the tasks are very short-lived, there will be a lot of contention for the work queue and throughput is dominated by the cost of synchronization. - Different QA methodologies are more effective at finding some types of defects and less effective at finding others. By employing complementary testing methodologies such as code review and static analysis, you can achieve greater confidence than you could with any single approach. - A synchronized block that calls notify or notifyAll but does not modify any state is likely to be an error. - Condition wait errors. When waiting on a condition queue, Object.wait or Condition. await should be called in a loop, with the appropriate lock held, after testing some state predicate (see Chapter 14). Calling Object.wait or Condition.await without the lock held, not in a loop, or without testing some state predicate is almost certainly an error. - Misuse of Lock and Condition. Using a Lock as the lock argument for a synchronized block is likely to be a typo, as is calling Condition.wait instead of await (though the latter would likely be caught in testing, since it would throw an IllegalMonitorStateException the first time it was called). - Sleeping or waiting while holding a lock. Calling Thread.sleep with a lock held can prevent other threads from making progress for a long time and is therefore a potentially serious liveness hazard. - Spin loops. Code that does nothing but spin (busy wait) checking a field for an expected value can waste CPU time and, if the field is not volatile, is not guaranteed to terminate. Latches or condition waits are often a better technique when waiting for a state transition to occur. - Before Java 5.0, the only mechanisms for coordinating access to shared data were synchronized and volatile. Java 5.0 adds another option: ReentrantLock. - Contrary to what some have written, ReentrantLock is not a replacement for intrinsic locking, but rather an alternative with advanced features for when intrinsic locking proves too limited. - Unlike intrinsic locking, Lock offers a choice of unconditional, polled, timed, and interruptible lock acquisition, and all lock and unlock operations are explicit. - ReentrantLock implements Lock, providing the same mutual exclusion and memory-visibility guarantees as synchronized. - Acquiring a ReentrantLock has the same memory semantics as entering a synchronized block, and releasing a ReentrantLock has the same memory semantics as exiting a synchronized block. - Intrinsic locking works fine in most situations but has some functional limitations—it is not possible to interrupt a thread waiting to acquire a lock, or to attempt to acquire a lock without being willing to wait for it forever. - Intrinsic locks also must be released in the same block of code in which they are acquired; this simplifies coding and interacts nicely with exception handling, but makes non-blockstructured locking disciplines impossible. None of these are reasons to abandon synchronized, but in some cases a more flexible locking mechanism offers better liveness or performance. - (You should always consider the effect of exceptions when using any form of locking, including intrinsic locking.) - Failing to use finally to release a Lock is a ticking time bomb. - This is one reason not to use ReentrantLock as a blanket substitute for synchronized: it is more "dangerous" because it doesn't automatically clean up the lock when control leaves the guarded block. - With intrinsic locks, a deadlock is fatal—the only way to recover is to restart the application, and the only defense is to construct your program so that inconsistent lock ordering is impossible. - Timed and polled locking offer another option: probabalistic deadlock avoidance. - soliciting - we saw how reducing lock granularity can enhance scalability. - The lock for a given node guards the link pointers and the data stored in that node, so when traversing or modifying the list we must hold the lock on one node until we acquire the lock on the next node; only then can we release the lock on the first node. An example of this technique, called hand-over-hand locking or lock coupling, appears in [CPJ 2.5.1.4]. - Java 6 uses an improved algorithm for managing intrinsic locks, similar to that used by ReentrantLock, that closes the scalability gap considerably. - Performance is a moving target; yesterday's benchmark showing that X is faster than Y may already be out of date today. - The ReentrantLock constructor offers a choice of two fairness options: create a nonfair lock (the default) or a fair lock. - (Semaphore also offers the choice of fair or nonfair acquisition ordering.) - Nonfair ReentrantLocks do not go out of their way to promote barging—they simply don't prevent a thread from barging if it shows up at the right time. - In most cases, the performance benefits of nonfair locks outweigh the benefits of fair queueing. - Don't pay for fairness if you don't need it. - One reason barging locks perform so much better than fair locks under heavy contention is that there can be a significant delay between when a suspended thread is resumed and when it actually runs. - Let's say thread A holds a lock and thread B asks for that lock. Since the lock is busy, B is suspended. When A releases the lock, B is resumed so it can try again. In the meantime, though, if thread C requests the lock, there is a good chance that C can acquire the lock, use it, and release it before B even finishes waking up. In this case, everyone wins: B gets the lock no later than it otherwise would have, C gets it much earlier, and throughput is improved. - Fair locks tend to work best when they are held for a relatively long time or when the mean time between lock requests is relatively long. In these cases, the condition under which barging provides a throughput advantage—when the lock is unheld but a thread is currently waking up to claim it—is less likely to hold. - deterministic - The language specification does not require the JVM to implement intrinsic locks fairly, and no production JVMs do. - ReentrantLock provides the same locking and memory semantics as intrinsic locking, as well as additional features such as timed lock waits, interruptible lock waits, fairness, and the ability to implement non-block-structured locking. - Reentrant-Lock is definitely a more dangerous tool than synchronization; if you forget to wrap the unlock call in a finally block, your code will probably appear to run properly, but you've created a time bomb that may well hurt innocent bystanders. - ReentrantLock is an advanced tool for situations where intrinsic locking is not practical. Use it if you need its advanced features: timed, polled, or interruptible lock acquisition, fair queueing, or non-block-structured locking. Otherwise, prefer synchronized. - Java 6 by providing a management and monitoring interface with which locks can register, enabling locking information for - The non-block-structured nature of ReentrantLock still means that lock acquisitions cannot be tied to specific stack frames, as they can with intrinsic locks. - Because synchronized is built into the JVM, it can perform optimizations such as lock elision for thread-confined lock objects and lock coarsening to eliminate synchronization with intrinsic locks (see Section 11.3.2); doing this with library-based locks seems far less likely. - Unless you are deploying on Java 5.0 for the foreseeable future and you have a demonstrated need for ReentrantLock's scalability benefits on that platform, it is not a good idea to choose ReentrantLock over synchronized for performance reasons. - Mutual exclusion is a conservative locking strategy that prevents writer/writer and writer/reader overlap, but also prevents reader/reader overlap. - As long as each thread is guaranteed an up-to-date view of the data and no other thread modifies the data while the readers are viewing it, there will be no problems. - This is what read-write locks allow: a resource can be accessed by multiple readers or a single writer at a time, but not both. - the read lock and write lock are simply different views of an integrated read-write lock object. - In practice, read-write locks can improve performance for frequently accessed read-mostly data structures on multiprocessor systems; under other conditions they perform slightly worse than exclusive locks due to their greater complexity. - Whether they are an improvement in any given situation is best determined via profiling; - it is relatively easy to swap out a readwrite lock for an exclusive one if profiling determines that a read-write lock is not a win. - Allowing readers to barge ahead of writers enhances concurrency but runs the risk of starving writers. - barge - Downgrading. If a thread holds the write lock, can it acquire the read lock without releasing the write lock? This would let a writer "downgrade" to a read lock without letting other writers modify the guarded resource in the meantime. - Most read-write lock implementations do not support upgrading, because without an explicit upgrade operation it is deadlock-prone. (If two readers simultaneously attempt to upgrade to a write lock, neither will release the read lock.) - ReentrantReadWriteLock provides reentrant locking semantics for both locks. Like ReentrantLock, a ReentrantReadWriteLock can be constructed as nonfair (the default) or fair. - Downgrading from writer to reader is permitted; upgrading from reader to writer is not (attempting to do so results in deadlock). - Like ReentrantLock, thewrite lock in ReentrantReadWriteLock has a unique owner and can be released only by the thread that acquired it. - Java 5.0, the read lock behaves more like a Semaphore than a lock, maintaining only the count of active readers, not their identities. This behavior was changed in Java 6 to keep track also of which threads have been granted the read lock. - Read-write locks can improve concurrency when locks are typically held for a moderately long time and most operations do not modify the guarded resources. - But ReentrantLock is not a blanket substitute for synchronized; use it only when you need features that synchronized lacks. - Read-write locks allow multiple readers to access a guarded object concurrently, offering the potential for improved scalability when accessing read-mostly data structures. - The client code in Listing 14.4 is not the only way to implement the retry logic. The caller could retry the take immediately, without sleeping—an approach known as busy waiting or spin waiting. This could consume quite a lot of CPU time if the buffer state does not change for a while. On the other hand, if the caller decides to sleep so as not to consume so much CPU time, it could easily "oversleep" if the buffer state changes shortly after the call to sleep. - A condition queue gets its name because it gives a group of threads—called the wait set—a way to wait for a specific condition to become true. - Unlike typical queues in which the elements are data items, the elements of a condition queue are the threads waiting for the condition. - Object.wait atomically releases the lock and asks the OS to suspend the current thread, allowing other threads to acquire the lock and therefore modify the object state. - Upon waking, it reacquires the lock before returning. Intuitively, calling wait means "I want to go to sleep, but wake me when something interesting happens", and calling the notification methods means "something interesting happened". -     // BLOCKS-UNTIL: not-full    public  synchronized  void put(V v) throws InterruptedException {        while (isFull())            wait();        doPut(v);        notifyAll();    }    // BLOCKS-UNTIL: not-empty    public  synchronized  V take() throws InterruptedException {        while (isEmpty())            wait();        V v = doTake();        notifyAll();        return v;    }} - Condition predicates are expressions constructed from the state variables of the class; - Document the condition predicate(s) associated with a condition queue and the operations that wait on them. - There is an important three-way relationship in a condition wait involving locking, the wait method, and a condition predicate. The condition predicate involves state variables, and the state variables are guarded by a lock, so before testing the condition predicate, we must hold that lock. The lock object and the condition queue object (the object on which wait and notify are invoked) must also be the same object. In BoundedBuffer, the buffer state is guarded by the buffer lock and the buffer object is used as the condition queue. The take method acquires the buffer lock and then tests the condition predicate - Every call to wait is implicitly associated with a specific condition predicate. When calling wait regarding a particular condition predicate, the caller must already hold the lock associated with the condition queue, and that lock must also guard the state variables from which the condition predicate is composed. - A single intrinsic condition queue may be used with more than one condition predicate. - When using condition waits (Object.wait or Condition.await): Always have a condition predicate—some test of object state that must hold before proceeding; Always test the condition predicate before calling wait, and again after returning from wait; Always call wait in a loop; Ensure that the state variables making up the condition predicate are guarded by the lock associated with the condition queue; Hold the lock associated with the the condition queue when calling wait, notify, or notifyAll; and Do not release the lock after checking the condition predicate but before acting on it. - marmalade - Whenever you wait on a condition, make sure that someone will perform a notification whenever the condition predicate becomes true. - There are two notification methods in the condition queue API—notify and notifyAll. - Calling notify causes the JVM to select one thread waiting on that condition queue to wake up; calling notifyAll wakes up all the threads waiting on that condition queue. - Because multiple threads could be waiting on the same condition queue for different condition predicates, using notify instead of notifyAll can be dangerous, primarily because single notification is prone to a problem akin to missed signals. - BoundedBuffer provides a good illustration of why notifyAll should be preferred to single notify in most cases. The condition queue is used for two different condition predicates: "not full" and "not empty". - Single notify can be used instead of notifyAll only when both of the following conditions hold: Uniform waiters. Only one condition predicate is associated with the condition queue, and each thread executes the same logic upon returning from wait; and One-in, one-out. A notification on the condition variable enables at most one thread to proceed. - Most classes don't meet these requirements, so the prevailing wisdom is to use notifyAll in preference to single notify. While this may be inefficient, it is much easier to ensure that your classes behave correctly when using notifyAll instead of notify. - If ten threads are waiting on a condition queue, calling notifyAll causes each of them to wake up and contend for the lock; then most or all of them will go right back to sleep. This means a lot of context switches and a lot of contended lock acquisitions for each event that enables (maybe) a single thread to make progress. (In the worst case, using notify-All results in O(n2) wakeups where n would suffice.) - This is another situation where performance concerns support one approach and safety concerns support the other. - The notification done by put and take in BoundedBuffer is conservative: a notification is performed every time an object is put into or removed from the buffer. This could be optimized by observing that a thread can be released from a wait only if the buffer goes from empty to not empty or from full to not full, and notifying only if a put or take effected one of these state transitions. This is called conditional notification. - conditional notification can improve performance, it is tricky to get right (and also complicates the implementation of subclasses) and so should be used carefully. - "First make it right, and then make it fast—if it is not already fast enough" - Listing 14.8. Using Conditional Notification in BoundedBuffer.put. public synchronized void put(V v) throws InterruptedException {    while (isFull())        wait();    boolean wasEmpty = isEmpty();    doPut(v);    if (wasEmpty)        notifyAll();} - A state-dependent class should either fully expose (and document) its waiting and notification protocols to subclasses, or prevent subclasses from participating in them at all. - (The worst thing a state-dependent class can do is expose its state to subclasses but not document its protocols for waiting and notification; this is like a class exposing its state variables but not documenting its invariants.) - One option for doing this is to effectively prohibit subclassing, either by making the class final or by hiding the condition queues, locks, and state variables from subclasses. - It is generally best to encapsulate the condition queue so that it is not accessible outside the class hierarchy in which it is used. - Wellings (Wellings, 2004) characterizes the proper use of wait and notify in terms of entry and exit protocols. For each state-dependent operation and for each operation that modifies state on which another operation has a state dependency, you should define and document an entry and exit protocol. - The entry protocol is the operation's condition predicate; the exit protocol involves examining any state variables that have been changed by the operation to see if they might have caused some other condition predicate to become true, and if so, notifying on the associated condition queue. - AbstractQueuedSynchronizer, upon which most of the state-dependent classes in java.util.concurrent are built (see Section 14.4), exploits the concept of exit protocol. - Just as Lock is a generalization of intrinsic locks, Condition (see Listing 14.10) is a generalization of intrinsic condition queues. - Intrinsic condition queues have several drawbacks. Each intrinsic lock can have only one associated condition queue, which means that in classes like BoundedBuffer multiple threads might wait on the same condition queue for different condition predicates, and the most common pattern for locking involves exposing the condition queue object. - A Condition is associated with a single Lock, just as a condition queue is associated with a single intrinsic lock; to create a Condition, call Lock.newCondition on the associated lock. - Hazard warning: The equivalents of wait, notify, and notifyAll for Condition objects are await, signal, and signalAll. However, Condition extends Object, which means that it also has wait and notify methods. Be sure to use the proper versions—await and signal—instead! - Just as with built-in locks and condition queues, the three-way relationship among the lock, the condition predicate, and the condition variable must also hold when using explicit Locks and Conditions. - The variables involved in the condition predicate must be guarded by the Lock, and the Lock must be held when testing the condition predicate and when calling await and signal.[11] Choose between using explicit Conditions and intrinsic condition queues in the same way as you would choose between - use Condition if you need its advanced features such as fair queueing or multiple wait sets per lock, and otherwise prefer intrinsic condition queues. (If you already use ReentrantLock because you need its advanced features, the choice is already made.) - In actuality, they are both implemented using a common base class, Abstract-QueuedSynchronizer (AQS)—as are many other synchronizers. - Listing 14.11. Bounded Buffer Using Explicit Condition Variables. @ThreadSafepublic class ConditionBoundedBuffer {    protected final Lock lock = new ReentrantLock();    // CONDITION PREDICATE: notFull (count < items.length)    private final Condition notFull    = lock.newCondition();    // CONDITION PREDICATE: notEmpty (count > 0)    private final Condition notEmpty  = lock.newCondition();    @GuardedBy("lock")    private final T[] items = (T[]) new Object[BUFFER_SIZE];    @GuardedBy("lock") private int tail, head, count;    // BLOCKS-UNTIL: notFull    public void put(T x) throws InterruptedException {        lock.lock();        try {            while (count == items.length)                notFull.await();            items[tail] = x;            if (++tail == items.length)                tail = 0;            ++count;            notEmpty.signal();        } finally {            lock.unlock();        }    }    // BLOCKS-UNTIL: notEmpty    public T take() throws InterruptedException {        lock.lock();        try {            while (count == 0)                notEmpty.await();            T x = items[head];            items[head] = null;            if (++head == items.length)                head = 0;            --count;            notFull.signal();            return x;        } finally {            lock.unlock();        }    }} - AQS handles many of the details of implementing a synchronizer, such as FIFO queuing of waiting threads. Individual synchronizers can define flexible criteria for whether a thread should be allowed to pass or be required to wait. - Using AQS to build synchronizers offers several benefits. Not only does it substantially reduce the implementation effort, but you also needn't pay for multiple points of contention, as you would when constructing one synchronizer on top of another. In SemaphoreOnLock, acquiring a permit has two places where it might block—once at the lock guarding the semaphore state, and then again if a permit is not available. Synchronizers built with AQS have only one point where they might block, reducing context-switch overhead and improving - The basic operations that an AQS-based synchronizer performs are some variants of acquire and release. - Release is not a blocking operation; a release may allow threads blocked in acquire to proceed. - The fast (uncontended) path for updating an atomic variable is no slower than the fast path for acquiring a lock, and usually faster; the slow path is definitely faster than the slow path for locks because it does not involve suspending and rescheduling threads. - With algorithms based on atomic variables instead of locks, threads are more likely to be able to proceed without delay and have an easier time recovering if they do experience contention. - The atomic variable classes provide a generalization of volatile variables to support atomic conditional read-modify-write operations. - AtomicInteger bears a superficial resemblance to an extended Counter class, but offers far greater scalability under contention because it can directly exploit underlying hardware support for concurrency. - Atomics as "Better Volatiles" -     public void setLower(int i) {        while (true) {            IntPair oldv = values.get();            if (i > oldv.upper)                throw new IllegalArgumentException(                   "Can't set lower to " + i + " > upper");            IntPair newv = new IntPair(i, oldv.upper);            if (values.compareAndSet(oldv, newv))                return;        }    }    // similarly for setUpper} 15.3.2. - at high contention levels locking tends to outperform atomic variables, but at more realistic contention levels atomic variables outperform locks.[6] This is because a lock reacts to contention by suspending threads, reducing CPU usage and synchronization traffic on the shared memory bus. (This is similar to how blocking producers in a producer-consumer design reduces the load on consumers and thereby lets them catch up.) - On the other hand, with atomic variables, contention management is pushed back to the calling class. Like most CAS-based algorithms, AtomicPseudoRandom reacts to contention by trying again immediately, which is usually the right approach but in a high-contention environment just creates more contention. - In practice, atomics tend to scale better than locks because atomics deal more effectively with typical contention levels. - With low to moderate contention, atomics offer better scalability; with high contention, locks offer better contention avoidance. (CAS-based algorithms also outperform lock-based ones on single-CPU systems, since a CAS always succeeds on a single-CPU system except in the unlikely case that a thread is preempted in the middle of the read-modify-write operation.) - it is often cheaper to not share state at all if it can be avoided. - We can improve scalability by dealing more effectively with contention, but true scalability is achieved only by eliminating contention entirely. - An algorithm is called nonblocking if failure or suspension of any thread cannot cause failure or suspension of another thread; an algorithm is called lock-free if, at each step, some thread can make progress. - An uncontended CAS always succeeds, and if multiple threads contend for a CAS, one always wins and therefore makes progress. - Nonblocking algorithms are also immune to deadlock or priority inversion (though they can exhibit starvation or livelock because they can involve repeated retries). - Nonblocking algorithms are considerably more complicated than their lock-based equivalents. - The key to creating nonblocking algorithms is figuring out how to limit the scope of atomic changes to a single variable while maintaining data consistency. - In linked collection classes such as queues, you can sometimes get away with expressing state transformations as changes to individual links and using an AtomicReference to represent each link that must be updated atomically. - compareAndSet provides both atomicity and visibility guarantees. - the counter and the stack, illustrate the basic pattern of using CAS to update a value speculatively, retrying if the update fails. - Listing 15.6. Nonblocking Stack Using Treiber's Algorithm (Treiber, 1986). - @ThreadSafepublic class ConcurrentStack  {    AtomicReference> top = new AtomicReference>();    public void push(E item) {        Node newHead = new Node(item);        Node oldHead;        do {            oldHead = top.get();            newHead.next = oldHead;        } while (!top.compareAndSet(oldHead, newHead)); - LinkedQueue in Listing 15.7 shows the insertion portion of the Michael-Scott nonblocking linked-queue algorithm (Michael and Scott, 1996), which is used by ConcurrentLinkedQueue. - quiescent - After the second update, the queue is again in the quiescent state, - circuitous - For frequently allocated, short-lived objects like queue link nodes, eliminating the creation of an AtomicReference for each Node is significant enough to reduce the cost of insertion operations. - AtomicStampedReference (and its cousin AtomicMarkableReference) provide atomic conditional update on a pair of variables. - AtomicStampedReference updates an object reference-integer pair, allowing "versioned" references that are immune[8] to the ABA problem. Similarly, AtomicMarkableReference updates an object reference-boolean pair that is used by some algorithms to let a node remain in a list while being marked as deleted. - Nonblocking algorithms maintain thread safety by using low-level concurrency primitives such as compare-and-swap instead of locks. These low-level primitives are exposed through the atomic variable classes, which can also be used as "better volatile variables" providing atomic update operations for integers and object references. - Nonblocking algorithms are difficult to design and implement, but can offer better scalability under typical conditions and greater resistance to liveness failures. - Java Memory Model (JMM) - Compilers may generate instructions in a different order than the "obvious" one suggested by the source code, or store variables in registers instead of in memory; processors may execute instructions in parallel or out of order; caches may vary the order in which writes to variables are committed to main memory; and values stored in processor-local caches may not be visible to other processors. - The Java Language Specification requires the JVM to maintain withinthread as-if-serial semantics: as long as the program has the same result as if it were executed in program order in a strictly sequential environment, all these games are permissible. - An architecture's memory model tells programs what guarantees they can expect from the memory system, and specifies the special instructions required (called memory barriers or fences) to get the additional memory coordination guarantees required when sharing data. - The classic sequential computing model, the von Neumann model, is only a vague approximation of how modern multiprocessors behave. - The bottom line is that modern shared-memory multiprocessors (and compilers) can do some surprising things when data is shared across threads, unless you've told them not to through the use of memory barriers. - The various reasons why operations might be delayed or appear to execute out of order can all be grouped into the general category of reordering. - Synchronization inhibits the compiler, runtime, and hardware from reordering memory operations in ways that would violate the visibility guarantees provided by the JMM.[1] - To guarantee that the thread executing action B can see the results of action A (whether or not A and B occur in different threads), there must be a happens-before relationship between A and B. - A correctly synchronized program is one with no data races; correctly synchronized programs exhibit sequential consistency, meaning that all actions within the program appear to happen in a fixed, global order. - Transitivity. If A happens-before B, and B happens-before C, then A happens-before C. - Even though actions are only partially ordered, synchronization actions—lock acquisition and release, and reads and writes of volatile variables—are totally ordered. - This makes it sensible to describe happens-before in terms of "subsequent" lock acquisitions and reads of volatile variables. - them—there is no happens-before relation between the actions in the two threads. - When one thread calls set to save the result and another thread calls get to retrieve it, the two had better be ordered by happens-before. - This could be done by making the reference to the result volatile, but it is possible to exploit existing synchronization to achieve the same result at lower cost. - FutureTask is carefully crafted to ensure that a successful call to tryReleaseShared always happens-before a subsequent call to tryAcquireShared; tryReleaseShared always writes to a volatile variable that is read by tryAcquireShared. -     V innerGet() throws InterruptedException, ExecutionException {        acquireSharedInterruptibly(0);        if (getState() == CANCELLED)            throw new CancellationException();        if (exception != null)            throw new ExecutionException(exception);        return result;    }} We call this technique "piggybacking" because it uses an existing happensbefore ordering that was created for some other reason to ensure the visibility of object X, rather than creating a happens-before ordering specifically for publishing X. - One thread putting an object on a queue and another thread subsequently retrieving it constitutes safe publication because there is guaranteed to be sufficient internal synchronization in a BlockingQueue implementation to ensure that the enqueue happens-before the dequeue. - Placing an item in a thread-safe collection happens-before another thread retrieves that item from the collection; - Counting down on a CountDownLatch happens-before a thread returns from await on that latch; Releasing a permit to a Semaphore happens-before acquiring a permit from that same Semaphore; - Submitting a Runnable or Callable to an Executor happens-before the task begins execution; - The safe publication techniques described there derive their safety from guarantees provided by the JMM; the risks of improper publication are consequences of the absence of a happens-before ordering between publishing a shared object and accessing it from another thread. - Unsafe publication can happen as a result of an incorrect lazy initialization, - Suppose thread A is the first to invoke getInstance. It sees that resource is null, instantiates a new Resource, and sets resource to reference it. When thread B later calls getInstance, it might see that resource already has a non-null value and just use the already constructed Resource. This might look harmless at first, but there is no happens-before ordering between the writing of resource in A and the reading of resource in B. - With the exception of immutable objects, it is not safe to use an object that has been initialized by another thread unless the publication happens-before the consuming thread uses it. - If thread A places X on a BlockingQueue (and no thread subsequently modifies it) and thread B retrieves it from the queue, B is guaranteed to see X as A left it. This is because the BlockingQueue implementations have sufficient internal synchronization to ensure that the put happens-before the take. Similarly, using a shared variable guarded by a lock or a shared volatile variable ensures that reads and writes of that variable are ordered by happens-before. - This happens-before guarantee is actually a stronger promise of visibility and ordering than made by safe publication. - UnsafeLazyInitialization can be fixed by making the getResource method synchronized, as shown in Listing 16.4. Because the code path through getInstance is fairly short (a test and a predicted branch), if getInstance is not called frequently by many threads, there is little enough contention for the SafeLazyInitialization lock that this approach offers adequate performance. - memory writes made during static initialization are automatically visible to all threads. - Thus statically initialized objects require no explicit synchronization either during construction or when being referenced. - However, this applies only to the as-constructed state—if the object is mutable, synchronization is still required by both readers and writers to make subsequent modifications visible and to avoid data corruption. - Listing 16.5. Eager Initialization. @ThreadSafe public class EagerInitialization {     private static Resource resource = new Resource();     public static Resource getResource() { return resource; } } Using eager initialization, shown in Listing 16.5, eliminates the synchronization cost incurred on each call to getInstance in SafeLazyInitialization. - Listing 16.6. Lazy Initialization Holder Class Idiom. @ThreadSafe public class ResourceFactory {      private static class ResourceHolder {          public static Resource resource = new Resource();      }      public static Resource getResource() {          return ResourceHolder.resource ;      } } 16.2.4. - DCL purported to offer the best of both worlds—lazy initialization without paying the synchronization penalty on the common code path. - And that's where the problem is: as described in Section 16.2.1, it is possible for a thread to see a partially constructed Resource. - The real problem with DCL is the assumption that the worst thing that can happen when reading a shared object reference without synchronization is to erroneously see a stale value (in this case, null); in that case the DCL idiom compensates for this risk by trying again with the lock held. But the worst case is actually considerably worse—it is possible to see a current value of the reference but stale values for the object's state, meaning that the object could be seen to be in an invalid or incorrect state. - the performance impact of this is small since volatile reads are usually only slightly more expensive than nonvolatile reads. - passed—the forces that motivated it (slow uncontended synchronization, slow JVM startup) are no longer in play, making it less effective as an optimization. - UnsafeLazyInitialization is actually safe if Resource is immutable.) - The Java Memory Model specifies when the actions of one thread on memory are guaranteed to be visible to another. # OReilly.Java.Performance.May.2014.ISBN.1449358454 - rationale for having separate generations - during the lengthy full GCs). G1 compacts the heap as it goes. - Hence, the first rule in sizing a heap is never to specify a heap that is larger than the amount of physical memory on the machine—and if there are multiple JVMs running, - good rule of thumb is to size the heap so that it is 30% occupied after a full GC. - calculate this, run the application until it has reached a steady-state configuration: a point at which it has loaded anything it caches, has created a maximum number of client connections, and so on. Then connect to the application with jconsole, force a full GC, and - that can be used to size the young generation: -XX:NewRatio= N Set the ratio of the young generation to the old generation. -XX:NewSize= N - -Xmn N Shorthand for setting both NewSize and MaxNewSize to the same value. - young generation is first sized by the NewRatio, which has a default value of 2. - By default, then, the young generation starts out at 33% of the initial heap size. - default for this flag (though PrintFlagsFinal will report a value of 1 MB). - is usually preferable to use -Xmn to specify a fixed size for the young generation as well. If - The young generation will grow in tandem with the overall heap size, but it can also fluctuate as a percentage of the total heap - bunch of class-related data, and that there are certain cir‐ - Note that permgen/metaspace does not hold the actual instance of the class (the Class objects), nor reflection objects (e.g., Method objects); those are held in the regular heap. - permgen/metaspace is really only used by the compiler and JVM run‐ time, and the data it holds is referred to as class metadata. There isn’t - One of the advantages to phasing out permgen is that the metaspace rarely needs to be sized—because (unlike permgen) metaspace will by default use as much space as it needs. - These memory regions behave just like a separate instance of the regular heap. They are sized dynamically based on an initial size and will increase as needed to a maximum size. For permgen, the sizes are specified via these flags: -XX:PermSize= N and -XX:MaxPermSize= N. Metaspace is sized with these flags: -XX:MetaspaceSize= N - All GC algorithms except the serial collector use multiple threads. The number of these threads is controlled by the -XX:ParallelGCThreads= N flag. The value of this flag affects the number of threads used for the following operations: - Take the example of a 16-CPU machine running four JVMs; each JVM will have by default 13 GC threads. If all four JVMs execute GC at the same time, the machine will have 52 CPU-hungry threads contending for CPU time. - 1. The basic number of threads used by all GC algorithms is based on the number of CPUs on a machine. 2. When multiple JVMs are run on a single machine, that num‐ ber will be too high and must be reduced. - To see how the JVM is resizing the spaces in an application, set the -XX:+PrintAdapti veSizePolicy flag. When a GC is performed, the GC log will contain information de‐ tailing how the various generations were resized - There are multiple ways to enable the GC log: specifying either of the flags -verbose:gc or -XX:+PrintGC will create a simple GC log (the flags are aliases for each other, and by default the log is disabled). The -XX:+PrintGCDetails flag will create a log with much more information. - it is often too difficult to diagnose what is happening with GC using only the simple log. In conjunc‐ tion with the detailed log, it is recommended to include -XX:+PrintGCTimeStamps or -XX:+PrintGCDateStamps, so that the time between GC operations can be determined. - Logfile rotation is controlled with these flags: -XX:+UseGCLogFileRotation -XX:NumberOfGCLogFiles= N -XX:GCLogFileSize= N. By default, UseGCLogFileRotation is disabled. When that flag - jstat provides nine options to print different information about the heap; jstat -options will provide the full list. - One useful option is -gcutil, which displays the time spent in GC as well as the per‐ centage of each GC area that is currently filled. Other options to jstat will display the GC sizes in terms of KB. - Figure 6-3. Throughput with various heap sizes - -XX:MaxGCPauseMillis= N and -XX:GCTimeRatio= N. - the usual effect of automatic heap sizing is that the heap (and generation) sizes will increase until the GCTimeRatio goal is met. - GC has a substantial impact on the perfor‐ mance of those applications, - with a hefty 28-second pause time. - Since the goal of CMS is to never have a full - good idea to start CMS with a larger initial heap size (and larger permgen/metaspace), which is a special case of making the heap larger to prevent those failures. - One way to let CMS win the race is to start the concurrent cycle sooner. If the concurrent cycle starts when 60% of the old generation is filled, CMS has a better chance of finishing than if the cycle starts when 70% of the old generation is filled. The - ParallelGCThreads flag: ConcGCThreads = (3 + ParallelGCThreads) / 4 - Avoiding concurrent mode failures is the key to achieving the best possible performance with CMS. - hits the value specified by -XX:CMSInitiatingPermOccupancyFraction= N, which defaults to 80%. Enabling permgen sweeping is only part of the story, - In Java 8, CMS does clean unloaded classes from the metaspace by default. If for some reason you wanted to disable that, unset the -XX:-CMSClassUnloadingEnabled flag (by default, it is true). - Incremental CMS (iCMS) is deprecated in Java 8—it still exists, but it may not be part - quad- core chip), the rational for iCMS becomes less important. On systems with limited CPU, consider the G1 collector instead—particularly since the background threads of G1 also will periodically pause during a background cycle, lim‐ iting the competition for the CPU. - This approach—clearing out only the mostly garbage regions —is what gives G1 its name: Garbage First. - As usual, the example log was taken using PrintGCDetails, but the details in the log for G1 are more verbose. - to make sure that the mixed GCs clean up enough memory to prevent future concurrent failures. - Humongous - that much. To that end, G1 is primarily tuned via a single flag: the same -XX:MaxGCPauseMillis= N flag that was used to tune the throughput collector. - of the stop-the-world phases of G1 start to exceed that value, G1 will attempt to compensate—adjusting the young-to-old ratio, adjusting the heap size, starting the background processing sooner, changing the tenuring threshold, - limit is called the tenuring threshold. - the best tenuring threshold is. The threshold starts at the value specified by the -XX:InitialTenuringThreshold= N flag (the default is 7 for the throughput and G1 - and the value specified by the -XX:MaxTenuringThreshold= N flag; for the throughput and G1 collectors, the default maximum threshold is 15, and for CMS it is 6. - circumvent - young collection will always be around for a long time, you can specify -XX:+AlwaysTenure (by default, false), which is essentially the same as setting the MaxTenuringThreshold to 0. This is a very, very rare situation; it means that - which can be added to the GC log by including the flag -XX:+PrintTenuringDistribution - The most important thing to look for is whether the survivor spaces are so small that during a minor GC, objects are promoted directly from eden into the old generation. - to remain in the young generation for a few GC cycles. This increases the probability the object will be freed before it is promoted to the old generation. - If the survivor spaces are too small, objects will promoted di‐ rectly into the old generation, - The best way to handle that situation is to increase the size of the heap (or at least the young generation) and allow the JVM to handle the survivor spaces. - The important thing to realize about TLABs is that they have a small size, so large objects cannot be allocated within a TLAB. - Large objects must be allocated directly from the heap, which requires extra time because of the synchronization. - Consider the case where a TLAB is 100 KB, and 75 KB has already been allocated. If a new 30 KB allocation is needed, the TLAB can be retired, which wastes 25 KB of eden space. Or the 30 KB - By default, TLABs are enabled; they can be disabled by specifying -XX:-UseTLAB, although they give such a performance boost that disabling them is always a bad idea. - total memory allocated for objects outside of TLABs is 568.32 MB. This is a case where either changing the application to use smaller objects, or tuning the JVM to allocate those objects in larger TLABs, can have a beneficial effect. - the -XX:+PrintTLAB flag to the command line. Then, at every young collection, the GC log will contain two kinds of line: a line for each thread describing the TLAB usage for that thread, and a summary line describing the overall - humongous - the G1 algorithm is designed around the idea that the number of regions is closer to 2,048. - Often, G1 will have to perform a full GC in order to find contiguous regions. - Because the humongous object is allocated directly in the old generation, it cannot be freed during a young collection. So if the object is short-lived, this also defeats the generational design of the collector. - If no contiguous regions are found, G1 will run a full GC: - Without the additional logging provided by ena‐ bling PrintAdaptiveSizePolicy, the standard G1 GC log does not provide enough information to diagnose this situation. - A better next step is to reduce the size of those objects rather than tune the JVM around them. - G1 considers an object to be humongous if it will fill more than 50% of a region. - Since G1 regions are always a power of 2, - G1 regions are sized in powers of 2, starting at 1 MB. - Heaps that have a very different maximum size than initial size will have too many G1 regions; the G1 region size should be increased in that case. - Packets have many qualities, but one thing they never do is lie. If - Almost all network devices and hosts use tables to make decisions. - Topologies and cabling are two other focal points providing further details into actual networking - A model is a way to organize a system’s functions and features to define its structural design. - Models are routinely organized in a hierarchical or layered structure. - The protocols are collectively referred to as a protocol suite. - The OSI model is called a reference model. - It is not the intent of this reference model to either serve as an implementation specification or to be a basis for appraising the conformance of actual implementations or to provide a sufficient level of detail to define precisely the services and protocols of the interconnection architecture. - Application Provides the sole means for the application to access the OSI environment (OSIE) with no layer above it. - The functions are divided into connection mode and connectionless mode. - This layer provides for the representation and preservation of the data provided by the Application Layer entities. - Specifically, the Presentation Layer is focused on syntax that is acceptable to both ends and access to the layers above and below. - Session Specifies both full-duplex and half-duplex modes of operation. This layer provides the means (setup and teardown) for communicating nodes to synchronize and manage the data between them. - A mapping is provided between the Transport Layer and Session Layer (session service access point) addresses. - Transport Protocols at this layer are end-to-end between communicating OSI nodes and deal primarily with low cost and reliable transfer of data. - Basic functions include transport connection establishment, release, data transfer, and QoS. While this layer is not responsible for routing, it does map to Network Layer addressing. - This layer is not responsible for negotiating QoS settings, but rather focuses on routing between networks and subnetworks. - In addition to interfacing with the Network Layer, the data link connection can be built upon one or more Physical Layer interfaces. - Like most models, this OSI Physical Layer contains the electrical, mechanical, and functional means to establish physical connections between Layer-2 devices. - Operator precedence is quite feeble in that it requires all the components of an expression to be analyzed - precedence - Colloquially, - trip over - A code source is a simple object that reflects the URL from which a class was loaded and the keys (if any) that were used to sign that class. Class loaders are responsible for creating and manipulating code source objects, - The basic entity that the access controller operates on is a permission object −− an instance of the Permission class (java.security.Permission). - The Permission class itself is an abstract class that represents a particular operation. - For example, if we construct a permission object that represents access to a file, possession of that object does not mean we have permission to access the file. Rather, possession of the object allows us to ask if we have permission to access the file. - Recall that permissions have three properties: a type, a name, and some actions. The name and actions are optional. The type corresponds to an actual Java type (e.g., java.io.FilePermission); the types that - the operations that are implemented on a permission object are not generally used in code that we write −− they are used instead by the access controller. - parentheses - This style of architecture promotes reuse at the macro (service) level rather than micro (classes) level. It - IBM Vice President of Web Services Michael Liebow says that SOA "builds highways".[26] - SOA promotes the goal of separating users - Reasons for treating the implementation of services as separate projects from larger projects include: - This advocates agility. That is to say, it fosters business innovations and speeds up time-to-market.[28] - What’s more, the most stymieing effect of these monolithic applications was ultimately that we were unable to keep pace with our partner’s innovation. - sequenced. - treasure - outdoing - adversary, - Strategic thinking is the art of outdoing an adversary, knowing that the adversary is trying to do the same to you. - Parents trying to elicit good behavior from children must become - We have replaced theoretical arguments with illustrative examples and case studies. - The book should be accessible to all readers who are willing to follow a little bit of arithmetic, charts, and tables. # JavaScript- The Good Parts - sidestep - Don't be discouraged if it takes multiple readings to get it. Your efforts will be rewarded. - journeyman programmer, - I discovered that I could be a better programmer by using only the good parts and avoiding the bad parts. - subset I carved out is vastly superior to the language as a whole, - enormous - The sooner we can detect and repair errors, the less they cost us. JavaScript is a loosely - JavaScript depends on global variables for linkage. - global variables are evil, - So, it is recommended that /* */ comments be avoided and // comments be used instead. In this book, // will be used exclusively. - Internally, it is represented as 64-bit floating point, the same as Java's double. - So 100 and 1e2 are the same number. - The value NaN is a number value that is the result of an operation that cannot produce a normal result. - NaN is not equal to any value, including itself. - so all characters in JavaScript are 16 bits wide. - Strings have a length property. For example, "seven".length is 5. - JavaScript throws them all together in a common global namespace. - the var statement defines the function's private variables. - Unlike many other languages, blocks in JavaScript do not create a new scope, so variables should be defined at the - The simple types of JavaScript are numbers, strings, booleans (true and false), null, and undefined. All other - In JavaScript, arrays are objects, functions are objects, regular expressions are objects, and, of course, objects are objects. - An object is a container of properties, where a property has a name and a value. A property name can be any string, including the empty string. A property value can be any JavaScript value except for undefined. Objects in JavaScript are class-free. There is no constraint on the names of new properties - Objects are useful for collecting and organizing data. Objects can contain other objects, so they can easily represent tree or graph structures. JavaScript includes a prototype linkage feature that allows one object to inherit the properties of another. When used well, this can reduce object - An object literal is a pair of curly braces surrounding zero or more name/value pairs. - anywhere an expression can appear: var empty_object = {};var stooge = {    "first-name": "Jerome",    "last-name": "Howard"}; - stooge["first-name"]     // "Joe"flight.departure.IATA    // "SYD" The undefined value is produced if an attempt is made to retrieve a nonexistent member: stooge["middle-name"]    // undefined - The || operator can be used to fill in default values: - var status = flight.status || "unknown"; - Attempting to retrieve values from undefined will throw a TypeError exception. This can be guarded against with the && operator: - flight.equipment.model                        // throw "TypeError"flight.equipment && flight.equipment.model    // undefined - Objects are passed around by reference. They are never copied: - The prototype link has no effect on updating. When we make changes to an object, the object's prototype is not touched: - The prototype link is used only in retrieval. If we try to retrieve a property value from an object, and if the object lacks the property name, then JavaScript attempts to - This is called delegation. - typeof flight.status      // 'string'typeof flight.arrival     // 'object'typeof flight.manifest    // 'undefined' - The other approach is to use the hasOwnProperty method, which returns true if the object has a particular property. The hasOwnProperty method does not look at the prototype chain: - flight.hasOwnProperty('number')         // trueflight.hasOwnProperty('constructor')    // false - are the hasOwnProperty method and using typeof to exclude functions: var name;for (name in another_stooge) {    if (typeof another_stooge[name] !== 'function') {        document.writeln(name + ': ' + another_stooge[name]); - Generally, the craft of programming is the factoring of a set of requirements into a set of functions and data structures. - Objects produced from object literals are linked to Object.prototype. Function objects are linked to Function.prototype (which is itself linked to Object.prototype). - Every function object is also created with a prototype property. Its value is an object with a constructor property whose value is the function. - The function object created by a function literal contains a link to that outer context. This is called closure. - important in object oriented programming, and its value is determined by the invocation pattern. There are four patterns of invocation in JavaScript: the method invocation pattern, the function invocation pattern, the constructor invocation pattern, and the apply invocation pattern. - The invocation operator is a pair of parentheses that follow any expression that produces a function value. - There is no runtime error when the number of arguments and the number of parameters do not match. If there are too many argument values, the extra argument values will be ignored. If there are too few argument values, the undefined value will be substituted for the - There is no type checking on the argument values: any type of value can be passed to any parameter. - var myObject = {    value: 0;    increment: function (inc) {        this.value += typeof inc === 'number' ? inc : 1;    }}; - Methods that get their object context from this are called public methods. - easy workaround. If the method defines a variable and assigns it the value of this, the inner function will have access to this through that variable. By convention, the name of that variable is that: // Augment myObject with a double method.myObject.double = function (  ) { -     var that = this;    // Workaround.    var helper = function (  ) {        that.value = add(that.value, that.value)    };    helper(  );    // Invoke helper as a function. - The language is class-free. This is a radical departure from the current fashion. - radical - JavaScript itself is not confident in its prototypal nature, so it offers an object-making syntax that is reminiscent of the classical languages. - reminiscent - If a function is invoked with the new prefix, then a new object will be created with a hidden link to the value of the function's prototype member, and this will be bound to that new object. - Functions that are intended to be used with the new prefix are called constructors. - // but we can invoke the get_status method on// statusObject even though statusObject does not have// a get_status method.var status = Quo.prototype.get_status.apply(statusObject);    // status is 'A-OK' - arguments is not really an array. It is an array-like object. arguments has a length property, but it lacks all of the array methods. - A function always returns a value. If the return value is not specified, then undefined is returned. - prefix and the return value is not an object, then this (the new object) is returned instead. - mishap - var add = function (a, b) {    if (typeof a !== 'number' || typeof b !== 'number') {        throw {            name: 'TypeError',            message: 'add needs numbers'        }    }    return a + b;} - The throw statement interrupts execution of the function. It should be given an exception object containing a name property that identifies the type of the exception, and a descriptive message property. You can also add other properties. - the ends of a string. That is an easy oversight to fix: String.method('trim', function (  ) {    return this.replace(/^\s+|\s+$/g, '');});document.writeln('"' + "   neat   ".trim(  ) + '"'); -     for (i = 0; i < nodes.length; i += 1) {        nodes[i].onclick = function (i) {            return function (e) {                alert(i);            };        }(i);    }}; - We can now define fibonacci with the memoizer, providing the initial memo array and fundamental function: var fibonacci = memoizer([0, 1], function (shell, n) { - a - The lineage of an object is irrelevant. - lineage - It can ape the classical pattern, - The set of possible inheritance patterns in JavaScript is vast. - JavaScript is a prototypal language, which means that objects inherit directly from other objects. - If you forget to include the new prefix when calling a constructor function, then this will not be bound to a new object. - clobbering - To mitigate this problem, there is a convention that all constructor functions are named with an initial capital, and that nothing else is spelled with an - this.prototype = {constructor: this}; - constructor property whose value is the new function object. The prototype object is the place where inherited traits are to be deposited. - (boldface text added for emphasis): - var coolcat = function (spec) {    var that = cat(spec),        super_get_name = that.superior('get_name');    that.get_name = function (n) {        return 'like ' + super_get_name(  ) + ' baby'; - JavaScript does not have anything like this kind of array. Instead, JavaScript provides an object that has some array-like - numbers inherits from Array.prototype, whereas number_object inherits from Object.prototype, so numbers inherits a larger set of useful methods. - JavaScript allows an array to contain any mixture of values: - The length property is the largest integer property name in the array plus one. This is not necessarily the number of properties in the array: - numbers.push('go');// numbers is ['zero', 'one', 'two', 'shi', 'go'] - ordinal - The first argument is an ordinal in the array. - numbers.splice(2, 1); - Since JavaScript's arrays are really objects, -         !(value.propertyIsEnumerable('length'));}; # Java Cryptography - Scott Oaks’ Java Security, - Let me say that again, every system can be broken. There are more secure and less secure systems, but no totally secure systems. - Building a secure application usually involves a three-way balancing act. The cost of having your application broken must be balanced against both the application’s cost and the application’s ease of use. - it will not make Java programs secure at the drop of a hat. - Cryptography is the science of secret writing. It’s a branch of mathematics, part of cryptology . - Proving identity is called authentication . In the physical world, a driver’s license is a kind of authentication. When you use a computer, you usually use a name and password to authenticate yourself. Cryptography provides stronger methods of authentication, called signatures and certificates. - Data transmitted across a network is subject to all sorts of nefarious attacks. - Cryptography can protect your data from thieves and impostors. - Applets are nifty, but without the right precautions they would be very dangerous. - Astute Inequalities - A message digest takes an arbitrary amount of input data and creates a short, digested version of the data, sometimes called a digital fingerprint, secure hash, or cryptographic hash. - Just as a fingerprint identifies a human, a message digest identifies data but reveals little about it. - Base64 is a system for representing an array of bytes as ASCII characters. This is useful, for example, when you want to send raw byte data through a medium, like email, that may not support anything but 7-bit ASCII. - A cipher is used to do this work. The cipher uses a key. Different keys will produce different results. SecretWriting stores its key in a file called SecretKey.ser. - Note that you must use the same key to encrypt and decrypt data. This is a property of a symmetric cipher. - Encryption is the process of taking data, called plaintext , and mathematically transforming it into an unreadable mess, called ciphertext . - The rot13 algorithm is a variation on the Caeser cipher, which, as its name implies, was hot stuff about 2000 years ago. - Symmetric Ciphers A symmetric cipher uses the same key at the sending and receiving end, as shown in Figure 2.3. - To avoid this problem, you could program each client with a different private key, but this would quickly become a distribution headache. - The shortcomings of symmetric ciphers are addressed by asymmetric ciphers, also called public key ciphers. - Public keys really are public; you can publish them in a newspaper or write them in the sky. - In some cases, the reverse of the process also works; data encrypted with the private key can be decrypted with the public key. - Asymmetric ciphers are much slower than symmetric ciphers, so they are not usually used to encrypt long messages. I’ll talk more about this later. - In practice, the cipher is a mathematical formula. A key is just a special number, or a few special numbers, that are used in the formula. - public key for an ElGamal cipher, for example, consists of three numbers, called p, g, and y. When you use an ElGamal cipher to encrypt data, the p, g, and y values are used mathematically to transform the plaintext into ciphertext. - Another solution for storing private keys is to put them on removable media, like floppy disks or smart cards. - Hybrid Systems Hybrid systems combine symmetric and asymmetric ciphers. - The beginning of a conversation involves some negotiation, carried out using an asymmetric cipher, where the participants agree on a private key, or session key . The session key is used with a symmetric cipher to encrypt the remainder of the conversation. - session key’s life is over when the two participants finish their conversation. If they have a new conversation, they’ll generate a new session key, which makes the cryptanalyst’s job harder. - Finally, symmetric ciphers are sometimes called secret key ciphers. - skullduggery, - This is a hefty batch of assumptions, - downloaded message digest, then eveything is copacetic, right? - The message digest becomes useful when it’s paired with other cryptographic techniques. A Message Authentication Code (MAC), for example, is basically a message digest with an associated key. - cipher. If Marian encrypts the message digest with her private key, Robin Hood can download the encrypted message digest, decrypt it using Marian’s public key, and compare the message digest to one that he computes from the downloaded file. If they match, then he can be sure that the file is correct. The encrypted message digest is called a signature ; Marian has signed the file. - that a message digest is a lot like a hash value, except longer. - Message digests are sometimes called secure hash functions or cryptographic hash functions. - Typically, an asymmetric cipher is used to authenticate the participants of a conversation; the conversation itself is encrypted with a symmetric cipher, using a special one-time key called a session key. - Essentially, a certificate is a signed public key. - Marian creates the certificate by placing some information about her, some information about Will, and Will’s public key value into a file. She then signs the file with her own private key, as shown in Figure 2.8. Robin Hood (or anyone else) can download this certificate and verify it using Marian’s public key. - The verification process is as follows: Calculate a message digest for the certificate contents (except the signature). Decrypt the signature using the signer’s (Marian’s) public key. The result is a message digest. Compare the decrypted message digest to the calculated message digest. If they match, the certificate is valid and you now know the value of Will’s public key. - Certificate Chains To verify a certificate, you need a public key. To verify a public key, you need a certificate. - Essentially, one certificate can be verified by another, which is verified by another, and so forth. This is called certificate chaining. The chain can’t be infinite, so where does it start? The certificate chain starts with a certificate whose issuer and subject are the same. - Usually such a certificate is issued by a Certificate Authority (CA), an ostensibly dependable institution like VeriSign or the U. S. Postal Service. - ostensibly - Robin Hood already has a trustworthy, self-signed certificate from Marian. He uses Marian’s public key to verify the signature on Friar Tuck’s certificate. Then he uses Friar Tuck’s public key to verify Little John’s certificate. Now, finally, he can trust Little John’s public key and use it to verify the integrity of the downloaded file. - Using certificates to prove authenticity, then, depends on a chain of certificates that ultimately terminates on a self-signed certificate issued by a CA. - Anyone can generate a self-signed certificate, claiming to be the Post Office or the Emperor of Tibet. Why would you ever trust a self-signed certificate? You can trust a self-signed certificate if you’re able to verify it. One convenient way to verify certificates is to calculate a message digest of the entire certificate, commonly known as a certificate fingerprint . To verify a fingerprint, call the people who issued the certificate and have them read off the numbers of the fingerprint. Another option is for the CA to widely publish their self-signed certificate’s fingerprint, perhaps in newspapers and magazines as well as online. - Currently, most self-signed certificates are embedded into web browsers. When you download and run a browser, it can recognize certificates issued by a dozen or so popular CAs, using internal self-signed certificates from these CAs. - a pseudo-random number generator (PRNG) as a source of “random” data. - SHA-1 produces a message digest value that is 160 bits long, which increases its resistance to attack. - In the version I’ll be using, blocks of plaintext are transformed into ciphertext using three DES keys and three applications of a normal DES cipher: The plaintext is encrypted using the first key. The result of step 1 is decrypted using the second key. The result of step 2 is encrypted using the third key, producing ciphertext. - PBE stands for passphrase-based encryption - In this particular variant of PBE, an MD5 message digest is used to digest the passphrase. - The digest value is then used as a DES key. One approach to this is described in PKCS#5, a document published by RSA Data Security, Inc. - The overall design of the cryptography classes is governed by the Java Cryptography Architecture - The JCE is an extension of the JCA and includes another cryptographic provider, called SunJCE. The JCE is a standard extension library, which means that although it is not a part of the core JDK, it is a package that works with the JDK. - The second group of methods is the Service Provider Interface, or SPI. This is the set of methods that subclasses must implement. By convention, SPI method names all begin with engine. - I suggest you bask in the simplicity of this style of programming. - At the root of the JCA is the idea of security providers. A provider supplies algorithms for the cryptographic concept classes. In practice, a provider is a collection of algorithm classes headed up by a java.security.Provider object. - This is confusing terminology; provider (small p) refers to the concept, while Provider refers to a specific class. - A factory method, then, is a special kind of static method that returns an instance of a class. In JDK 1.0.2, factory methods were used indirectly in the Socket class (see setSocketImplFactory()). - The Security class keeps track of providers by keeping a list of their corresponding Provider objects. When it needs a particular algorithm, it asks each Provider, in turn, if it implements a particular algorithm. Each Provider knows about the other classes in the provider’s repertoire and will return an appropriate instance if possible. The Provider is, in effect, the boss of the algorithm team. - To configure providers statically, you’ll need to edit the java.security file, which is found in the lib/security directory underneath your main JDK installation directory. - Instead, they rely on a pseudo-random number generator (PRNG). A cryptographically strong PRNG, seeded with truly random values, is a PRNG that does a good job of spewing out unpredictable data. - The JDK includes a class, java.util.Random, that implements a PRNG. Although it’s fine for light-duty use, it has the following shortcomings: It uses an algorithm that produces a predictable sequence of numbers. - Because of the irreversible nature of the message digest, it’s very hard to predict the past and future values of the PRNG even if you know its present output. - The thread timing algorithm is not thoroughly tested. It may have weaknesses that cryptanalysts could exploit. - It relies on counting the number of times that the calling thread can yield while waiting for another thread to sleep for a specified interval. - PGP (Pretty Good Privacy, a popular cryptography application). - Several interfaces extend the Key interface. These child interfaces define different flavors of keys, but none of them defines any additional methods; they are used for clarity and type safety. - The JCE includes another semantic extension of Key: javax.crypto.SecretKey This interface represents a secret (or private, or session) key that is used for a symmetric cipher. With a symmetric cipher, the same secret key is used to encrypt and decrypt data. - There are two varieties of key generators. The first generates key pairs for use with asymmetric ciphers and signatures. The second kind generates a single key for use with a symmetric cipher. - public SecretKeySpec(byte[] key, String algorithm) This constructor creates a SecretKeySpec using the supplied byte array. The key will have the supplied algorithm. public SecretKeySpec(byte[] key, int offset, int len, String algorithm) This constructor creates a SecretKeySpec using len bytes of the supplied byte array, starting at - Use this method to create a new SecretKeyFactory for the given algorithm. The algorithm name should correspond to a symmetric cipher algorithm name, for example, “DES.” - From things to keys To translate a KeySpec into a SecretKey, use SecretKeyFactory’s generateSecret() method: - KeyFactory java.security.KeyFactory is a lot like SecretKeyFactory, except that it deals with public and private keys instead of secret keys. - A key agreement is a protocol whereby two or more parties can agree on a secret value. The neat thing about key agreements is that they can agree on a secret value even while talking on an insecure medium (like the Internet). These protocols are called key agreement protocols because they are most often used to settle on a session key that will be used to encrypt a conversation. - The most famous key agreement protocol is Diffie-Hellman (DH). - a paper that is widely considered to be the genesis of public key cryptography. - The SunJCE provider includes a KeyAgreement implementation based on Diffie-Hellman. - public static final KeyAgreement getInstance(String algorithm) throws NoSuchAlgorithmException This method creates a new KeyAgreement for the given algorithm. The name should be a key agreement name, like “DH” for Diffie-Hellman. - As I said, the base and modulus used in Diffie-Hellman may be dictated by a standard. One such standard is Simple Key Management for Internet Protocols (SKIP).[ - SKIP defines base and modulus values for three different sizes of Diffie-Hellman keys. We’ll use the 1024-bit base and modulus. - hexadecimal. - Each Identity contains a PublicKey and other relevant information (name, address, phone number, etc.). Each Signer contains a matched PublicKey and PrivateKey and other useful information. - Key Holders Keys usually belong to something—a person, a group of people, a company, a computer, a thread of execution, or almost anything else. In the JDK, the java.security.Identity class represents something that possesses a key. - Identity An Identity represents a person, an organization, or anything else that has an associated public key. In other words, an Identity is a Principal with a public key. - JDK 1.2 offers a new method for key management, based on java.security.KeyStore . A KeyStore is a handy box that holds keys and certificates. One KeyStore contains all the information a single person (or application, or identity) needs for authentication. - A KeyStore contains two types of entries. The first type contains a private key and a chain of certificates that correspond to the matching public key. I’ll call this type of entry a private key entry. - KeyStore holds all this information, organized by aliases, or short names. Entries are stored and retrieved using an alias, similar to the way a Hashtable or Properties object works. - KeyStore’s getInstance() method uses a line in the java.security properties file to decide what subclass of KeyStore to create. The line might look like this: keystore=oreilly.jonathan.security.SuperDuperKeyStore - This is a different use of a passphrase from what we saw earlier, with store() and load(). In those methods, a passphrase is used to protect the integrity of the keystore data as a whole. Here, a passphrase is used for confidentiality, to obscure a private key. - keytool keytool is a command-line interface to the java.security.KeyStore class. As we’ve seen, a KeyStore is a simple database for private keys, public keys, and certificates. Each entry in the KeyStore has an alias that identifies it. Entries are always referenced using an alias. - If you don’t specify a KeyStore file when using keytool, the default file will be used. This is a file called .keystore, located in the directory determined by the HOMEDRIVE and HOMEPATH environment variables. - concatenated; - -dname This entry is used to specify a distinguished name (DN).[13] A DN contains your name and places you in a hierarchy based on countries and organizations (companies, universities, etc.). In the preceding example, I’ve identified my real name, my company, my group within the company (Technical Publications), and the country I live in. Here is a complete list of DN fields that keytool recognizes: CN (common name): your name OU (organizational unit): the part of your organization to which you belong O (organization): your organization L (locality): usually, a city S (state): a state or province C (country): a country You don’t have to include every DN field. - This passphrase is used to protect the private key of the new key pair. - You will have to type the same passphrase to access the private key at a later date. - Inspecting the keystore To see the contents of a keystore, use the -list command: - Generating a CSR To get a real certificate, signed by a Certificate Authority (CA), you need to generate a Certificate Signing Request (CSR). The CSR is a special file that contains your public key and information about you. It is signed with your private key. When you send a CSR to a CA, the CA will make some effort to verify your identity and to verify the authenticity of the CSR. - Then it can issue you a certificate, signed with the CA’s private key, that verifies your public key. - So what does the CSR look like? Basically it’s just a long string of base64 data. You can send it to your CA via FTP, HTTP, or email. - You authenticate yourself using a personal identification number (PIN). The PIN is a shared secret, something that both you and the bank know. - have none of the usual visual or aural clues that are helpful in everyday transactions. - Message digests produce a small “fingerprint” of a larger set of data. - Digital signatures can be used to prove the integrity of data. - Certificates are used as cryptographically safe containers for public keys. - The Java Cryptography Architecture (JCA) makes it very easy to use message digests. - To obtain a MessageDigest for a particular algorithm use one of its getInstance() factory methods: public static MessageDigest getInstance(String algorithm) throws NoSuchAlgorithmException This method returns a MessageDigest for the given algorithm. - Feeding To feed data into the MessageDigest, use one of the update() methods: public void update(byte input) This method adds the specified byte to the message digest’s input data. - Digesting To find out the digest value, use one of the digest() methods: public byte[] digest() The value of the message digest is returned as a byte array. public byte[] digest(byte[] input) This method is provided for convenience. - you can reuse the MessageDigest for a second set of data by clearing its internal state first. public void reset() This method clears the - you can calculate a message digest value for any input data with just a few lines of code: // Define byte[] inputData first. MessageDigest md = MessageDigest.getInstance("SHA"); md.update(inputData); byte[] digest = md.digest(); - Message digests are one of the building blocks of digital signatures. - The password is a shared secret because both the user and the server must know it. - Most computer networks, however, are highly susceptible to eavesdropping, so this is not a very secure solution. - If the two message digests are equal, then the client is authenticated. This simple procedure, however, is vulnerable to a replay attack. A malicious user could listen to the digested password and replay it later to gain illicit access to the server. - To avoid this problem, some session-specific information is added to the message digest. In particular, the client generates a random number and a timestamp and includes them in the digest. These values must also be sent, in the clear, to the server, so that the server can use them to calculate a matching digest value. The server must be programmed to receive the extra information and include it in its message digest calculations. Figure 6.1 shows how this works on the client side. Figure 6-1. Protecting a password The server uses the given name to look up the password in a private database. Then it uses the given name, random number, timestamp, and the password it just retrieved to calculate a message digest. If this digest value matches the digest sent by the client, the client has been authenticated. - Double-Strength Password Login There is a stronger method for protecting password information using message digests. It involves an additional timestamp and random number, - First, a digest is computed, just as in the previous example. Then, the digest value, another random number, and another timestamp are fed into a second digest. Then the server is sent the second digest value, along with the timestamps and random numbers. - Why is this better than the simpler scheme we outlined earlier? To understand why, think about how you might try to break the protected password scheme. Recall that a message digest is a one-way function; ideally, this means that it’s impossible to figure out what input produced a given digest value.[ - Neither the regular or double-strength login methods described here prevent a dictionary attack on the password. - A message authentication code (MAC) is basically a keyed message digest. Like a message digest, a MAC takes an arbitrary amount of input data and creates a short digest value. Unlike a message digest, a MAC uses a key to create the digest value. This makes it useful for protecting the integrity of data that is sent over an insecure network. - Calculating the Code To actually calculate the MAC value, use one of the doFinal() methods: public final byte[] doFinal() throws IllegalStateException - SecureRandom sr = new SecureRandom(); byte[] keyBytes = new byte[20]; sr.nextBytes(keyBytes); SecretKey key = new SecretKeySpec(keyBytes, "HmacSHA1"); Mac m = Mac.getInstance("HmacSHA1"); m.init(key); m.update(inputData); byte[] mac = m.doFinal(); - A signature provides two security services, authentication and integrity. A signature gives you assurance that a message has not been tampered with and that it originated from a certain person. - a signature is a message digest that is encrypted with the signer’s private key. - Only the signer’s public key can decrypt the signature, which provides authentication. If the message digest of the message matches the decrypted message digest from the signature, then integrity is also assured. - Signatures are useful for distributing software and documentation because they foil forgery. - Generating a Signature Generating a signature is a lot like generating a message digest value. The sign() method returns the signature itself: public final byte[] sign() throws - To generate a signature, you will need the signer’s private key and the message that you wish to sign. The procedure is straightforward: Obtain a Signature object using the getInstance() factory method. You’ll need to specify an algorithm. A signature actually uses two algorithms—one to calculate a message digest and one to encrypt the message digest. The SUN provider shipped with the JDK 1.1 supports DSA encryption of an SHA-1 message digest. This is simply referred to as DSA. Initialize the Signature with the signer’s private key using initSign(). Use the update() method to add the data of the message into the signature. You can call update() as many times as you would like. Three different overloads allow you to update the signature with byte data. Calculate the signature using the sign() method. This method returns an array of bytes that are the signature itself. It’s up to you to store the signature somewhere. Verifying a Signature You can use Signature’s verify() method to verify a signature: public final boolean verify(byte[] signature) throws - Check if your signatures match using the verify() method. This method accepts an array of bytes that are the signature to be verified. It returns a boolean value that is true if the signatures match and false otherwise. - We’ll look at the simple case, with a pair of programs called StrongClient and StrongServer. StrongClient creates a timestamp and a random number and sends them along with the user’s name and a signature to the server. The length of the signature is sent before the signature itself, just as it was with the message digest login examples. - One possible application of SignedObject is in the last example. We might write a simple class, AuthorizationToken, that contained the user’s name, the timestamp, and the random value. This object, in turn, could be placed inside a SignedObject that could be passed from client to server. - Certificates To verify a signature, you need the signer’s public key. So how are public keys distributed securely? You could simply download the key from a server somewhere, but how would you know you got the right file and not a forgery? Even if you get a valid key, how do you know that it belongs to a particular person? - A certificate is a statement, signed by one person, that the public key of another person has a particular value. In some ways, it’s like a driver’s license. The license is a document issued by your state government that matches your face to your name, address, and date of birth. - You need to trust the person who issued the certificate (who is known as a Certificate Authority, or CA). - In cryptographic terminology, a certificate associates an identity with a public key. The identity is called the subject . The identity that signs the certificate is the signer. The certificate contains information about the subject and the subject’s public key, plus information about the signer. The whole thing is cryptographically signed, and the signature becomes part of the certificate, too. Because the certificate is signed, it can be freely distributed over insecure channels. - At a basic level, a certificate contains these elements: Information about the subject The subject’s public key Information about the issuer The issuer’s signature of the above information - Sun recognized that certificate support was anemic in JDK 1.1. Things are improved in JDK 1.2. - Working with certificates in JDK 1.2 is sometimes difficult because there are two things named Certificate. The java.security.Certificate interface was introduced in JDK 1.1, but it’s now deprecated. The “official” certificate class in JDK 1.2 is java.security.cert.Certificate. - public abstract void verify(PublicKey key) throws CertificateException, NoSuchAlgorithmException, InvalidKeyException, NoSuchProviderException, SignatureException This method uses the supplied public key to verify the certificate’s contents. The public key should belong to the certificate’s issuer (and has nothing to do with the public key contained in this certificate). The supplied issuer’s public key is used to verify the internal signature that protects the integrity of the certificate’s data. - X.509 Several standards specify the contents of a certificate. One of the most popular is X.509, published by the International Telecommunications Union (ITU). - To load an X.509 certificate from a file, you can use getInstance() : public static final X509Certificate getInstance(InputStream inStream) throws CertificateException - cert.provider.x509=sun.security.x509.X509CertImpl Let’s say you call getInstance() with an input stream. A sun.security .x509.X509CertImpl will be created, using a constructor that accepts the input stream. It’s up to the X509CertImpl to read data from the input stream to initialize itself. X509CertImpl knows how to construct itself from a DER-encoded certificate. What is DER? In the X.509 standard, a certificate is specified as a data structure using the ASN.1 (Abstract Syntax Notation) language. There are a few different ways that ASN.1 data structures can be reduced to a byte stream, and DER (Distinguished Encoding Rules) is one of these methods. The net result is that an X509CertImpl can recognize an X.509 certificate if it is - Let’s look at an example that uses X509Certificate . We’ll write a tool that displays information about a certificate contained in a file, just like keytool -printcert. Like keytool, we’ll recognize certificate files in the format described by RFC 1421. An RFC 1421 certificate representation is simply a DER representation, converted to base64, with a header and a footer line. Here is such a file: -----BEGIN CERTIFICATE----- MIICMTCCAZoCAS0wDQYJKoZIhvcNAQEEBQAwXDELMAkGA1UEBhMCQ1oxETAPBgNV - Our class performs three tasks: We need to read the file, strip off the header and footer, and convert the body from a base64 string to a byte array. The oreilly.jonathan.util.Base64 class is used to perform the base64 conversion. This class is presented in Appendix B. We’ll use this byte array (a DER-encoded certificate) to create a new X509Certificate. We can then print out some basic information about the certificate. Finally, we’ll calculate certificate fingerprints and print them. - shortcoming of the JDK 1.1 certificate support: Certificate Revocation Lists (CRLs). CRLs answer the question of what happens to certificates when they’re lost or stolen. - A CRL is simply a list of certificates that are no longer valid. - public abstract boolean isRevoked(BigInteger serialNumber) This method returns true if the certificate matching the given serial number has been revoked. Serial numbers are unique to a Certificate Authority (CA). Each CA issues its own CRLs. Thus, this method is used to correlate certificate serial numbers from the same CA. - A cipher encrypts or decrypts data. Ciphers comes in three flavors: Symmetric , or private key , ciphers use a single secret key to encrypt and decrypt data. Symmetric keys can be useful in applications like hard-disk file encryption, when the same person encrypts and decrypts data. Asymmetric , or public key , ciphers use a pair of keys. One key is public and may be freely distributed. The other key is private and should be kept secret. Data encrypted with either key can be decrypted using the other key. Hybrid systems use a combination of symmetric and asymmetric ciphers. Asymmetric ciphers are much slower than their symmetric counterparts. In a hybrid system, an asymmetric cipher is used to exchange a private key (also called a secret key or a session key). The secret key is used with a symmetric cipher for data encryption and decryption. - This list mixes apples and oranges a little bit. - Asymmetric ciphers are block ciphers. Before computers, encryption was accomplished using stream ciphers, which are ciphers that operate on one character of a message at a time. - PKCS#5 PKCS#5 is one possible padding scheme. PKCS#5 is a Public-Key Cryptography Standard, a self-proclaimed standard published by RSA Data Security, Inc. The padding method is straightforward: Fill the remainder of the block with bytes containing the number of remaining bytes.[ - the name for PKCS#5 padding is “PKCS5Padding.” - The mode of a cipher determines how blocks of plaintext are encrypted into blocks of ciphertext, and vice versa. You can find out the mode of a Cipher by calling getMode(). The SunJCE provider supports ECB, CBC, CFB, OFB, and PCBC modes, which I will describe here. - ECB The simplest case is electronic code book (ECB) mode, in which each block of plaintext encrypts to a block of ciphertext. - ECB mode has the disadvantage that the same plaintext will always encrypt to the same ciphertext, if you use the same key. - If your data is more “random looking,” like a key or a message digest, then ECB may be appropriate. Otherwise, you should consider a different mode. - Cipher block chaining (CBC) mode overcomes the weakness of ECB mode. Each block of plaintext is combined with the previous block’s ciphertext, using XOR; the result is encrypted to form a block of ciphertext. - Because there is no previous ciphertext block for the first block of plaintext, an initialization vector (IV) is used for the first block of plaintext. The IV is usually just random data. The decrypting cipher must be initialized with the same IV to correctly decrypt the data. - PCBC Propagating cipher block chaining (PCBC) mode is a lot like CBC mode. When a plaintext block is encrypted, however, it is XORed with both the previous plaintext block and the previous ciphertext block. Likewise, decrypted blocks are XORed with the previous plaintext and ciphertext blocks. - Cipher feedback (CFB) mode allows a block cipher to act like a stream cipher. Like CBC, it uses an IV, but the internal process is more involved. - As you might have noticed, CFB mode is not particularly efficient. Each time a piece of plaintext is encrypted, an entire block is encrypted by the underlying cipher. - For a cipher with a block size of 64 bits, CFB8 will be about eight times slower than ECB or CBC. - You can use CFB mode with any symmetric block cipher. Interestingly, you can use CFB mode with an asymmetric cipher algorithm, too, but it will behave like a symmetric cipher. - OFB Output feedback (OFB) mode works just like CFB mode, except in how the internal buffer is updated. - When the internal buffer is shifted left, the space on the right side is filled with the leftmost bits of the encrypted buffer (instead of the ciphertext, which was used in CFB). - PKCS#5 is actually a standard for passphrase-based encryption. Part of the standard specifies this padding scheme. You can get PKCS#5 from RSA Data Security, - The ciphertext is represented in base64, which uses 6 bits per digit. Thus, the first 10 digits make up 60 bits of the first 64-bit ciphertext block, and these digits are the same for both ciphertexts. - Algorithms One of the nice features of the provider architecture in the Security API is that it’s possible to use different cryptographic algorithms without having to rewrite your program. The SunJCE provider includes three cipher algorithms. - The javax.crypto.Cipher class encapsulates a cipher algorithm. A Cipher either encrypts data or decrypts data. The Cipher class encompasses both asymmetric (public key) and symmetric (private key) algorithms. - Salt is additional data concatenated to the passphrase. The passphrase and salt are digested together. This means that the attacker’s dictionary now needs to contain many more entries, one for each possible salt value for each probable passphrase. # Java Performance: The Definitive Guide - The G1 young collection is triggered when eden fills up - collectors. As usual, the example log was taken using PrintGCDetails, but the details in the log for G1 are more verbose. - As is usual for a young collection, G1 has completely emptied eden and adjusted the survivor spaces. Additionally, two of the marked regions have been collected. Those regions were known to contain mostly garbage, and so a large part of them was freed. Any live data in those regions was moved to another region (just as live data was moved from the young generation into regions in the old generation). This is why G1 ends up with a fragmented heap less often than CMS—moving the objects like this is compacting the heap as G1 goes along. - G1 has completed a marking cycle and has started performing mixed GCs to clean up the old regions, but the old generation runs out of space before enough memory can be reclaimed from the old generation. In the log, a full GC immediately follows a mixed GC: - G1 has a number of cycles (and phases within the concurrent cycle). A well-tuned JVM running G1 should only experience young, mixed, and concurrent GC cycles. - Small pauses occur for some of the G1 concurrent phases. G1 should be tuned if necessary to avoid full GC cycles. - To that end, G1 is primarily tuned via a single flag: the same -XX:MaxGCPauseMillis=N flag that was used to tune the throughput collector. When used with G1 (and unlike the throughput collector), that flag does have a default value: 200 ms. If pauses for any of the stop-the-world phases of G1 start to exceed that value, G1 will attempt to compensate—adjusting the young-to-old ratio, adjusting the heap size, starting the background processing sooner, changing the tenuring threshold, and (most significantly) processing more or fewer old generation regions during a mixed GC cycle. The usual trade-off - To have G1 win its race, try increasing the number of background marking threads (assuming there is sufficient CPU available on the machine). Tuning the G1 threads is similar to tuning the CMS threads: the ParallelGCThreads option affects the number of threads used for phases when application threads are stopped, and the ConcGCThreads flag affects the number of threads used for concurrent phases. - G1 can also win its race if it starts collecting earlier. The G1 cycle begins when the heap hits the occupancy ratio specified by -XX:InitiatingHeapOccupancyPercent=N, which has a default value of 45. Note that unlike CMS, that setting is based on the usage of the entire heap, not just the old generation. - a region is declared eligible for collection during a mixed GC if it is 35% garbage. (It is likely this value will become a tunable parameter at some point; the experimental name for the parameter (available in experiment builds of the open source code) is -XX:G1MixedGCLiveThresholdPercent=N.) - G1 tuning should begin by setting a reasonable pause time target. - To make the background threads run more frequently, adjust the InitiatingHeapOccupancyPercent. If additional CPU is available, adjust the number of threads via the ConcGCThreads flag. - To prevent promotion failures, decrease the size of the G1MixedGCCountTarget. - This is the reason that the young generation is divided into two survivor spaces and eden. This setup allows objects to have some additional chances to be collected while still in the young generation, rather than being promoted into (and filling up) the - When the young generation is collected and the JVM finds an object that is still alive, that object is moved to a survivor space rather than to the old generation. During the first young generation collection, objects are moved from eden into survivor space 0. During the next collection, live objects are moved from both survivor space 0 and from eden into survivor space 1. At that point, eden and survivor space 0 are completely empty. The next collection moves live objects from survivor space 1 and eden into survivor space 0, and so on. - (The survivor spaces are also referred to as the “to” and “from” spaces; during each collection, objects are moved out of the “from” space into the “to” space. “from” and “to” are simply pointers that switch between the two survivor spaces on every collection.) - Clearly this cannot continue forever, or nothing would ever be moved into the old generation. Objects are moved into the old generation in two circumstances. First, the survivor spaces are fairly small. When the target survivor space fills up during a young collection, any remaining live objects in eden are moved directly into the old generation. Second, there is a limit to the number of GC cycles during which an object can remain in the survivor spaces. That limit is called the tenuring threshold. - The survivor spaces take up part of the allocation for the young generation, and like other areas of the heap, the JVM sizes them dynamically. The initial size of the survivor spaces is determined by the -XX:InitialSurvivorRatio=N flag, which is used in this equation: survivor_space_size = new_size / (initial_survivor_ratio + 2) For the default initial survivor ratio of 8, each survivor space will occupy 10% of the young generation. - To keep the survivor spaces at a fixed size, set the SurvivorRatio to the desired value and disable the UseAdaptiveSizePolicy flag (though remember that disabling adaptive sizing will apply to the old and new generations as well). - The JVM determines whether to increase or decrease the size of the survivor spaces (subject to the defined ratios) based on how full a survivor space is after a GC. - The survivor spaces will be resized so that they are, by default, 50% full after a GC. That value can be changed with the -XX:TargetSurvivorRatio=N flag. - The threshold starts at the value specified by the -XX:InitialTenuringThreshold=N flag (the default is 7 for the throughput and G1 collectors, and 6 for CMS). The JVM will ultimately determine a threshold between 1 and the value specified by the -XX:MaxTenuringThreshold=N flag; for the throughput and G1 collectors, the default maximum threshold is 15, and for CMS it is 6. - If you know that objects that survive a young collection will always be around for a long time, you can specify -XX:+AlwaysTenure (by default, false), which is essentially the same as setting the MaxTenuringThreshold to 0. This is a very, very rare situation; it means that objects will always be promoted to the old generation rather than stored in a survivor space. - -XX:+NeverTenure (also false by default). This flag affects two things: it behaves as if the initial and max tenuring thresholds are infinity, and it prevents the JVM from adjusting that threshold down. In other words, as long as there is room in the survivor space, no object will ever be promoted to the old generation. - Given all that, which values might be tuned under which circumstances? It is helpful to look at the tenuring statistics, which can be added to the GC log by including the flag -XX:+PrintTenuringDistribution (which is false by default). - The most important thing to look for is whether the survivor spaces are so small that during a minor GC, objects are promoted directly from eden into the old generation. The reason to avoid that is short-lived objects will end up filling the old generation, causing full GCs to occur too frequently. - Survivor spaces are designed to allow objects (particularly just-allocated objects) to remain in the young generation for a few GC cycles. This increases the probability the object will be freed before it is promoted to the old generation. - If the survivor spaces are too small, objects will promoted directly into the old generation, which in turn causes more old GC cycles. - The best way to handle that situation is to increase the size of the heap (or at least the young generation) and allow the JVM to handle the survivor spaces. - In rare cases, adjusting the tenuring threshold or survivor space sizes can prevent promotion of objects into the old generation. - one reason allocation in eden is so fast is that each thread has a dedicated region where it allocates objects—a TLAB. - By setting up each thread with its own dedicated allocation area, the thread needn’t perform any synchronization when allocating objects. (This is a variation of how thread-local variables can prevent lock contention [see Chapter 9].) - The important thing to realize about TLABs is that they have a small size, so large objects cannot be allocated within a TLAB. Large objects must be allocated directly from the heap, which requires extra time because of the synchronization. - At this point, the JVM has a choice. One option is to “retire” the TLAB and allocate a new one for the thread. Since the TLAB is just a section within eden, the retired TLAB will be cleaned at the next young collection and can be reused subsequently. - Consider the case where a TLAB is 100 KB, and 75 KB has already been allocated. If a new 30 KB allocation is needed, the TLAB can be retired, which wastes 25 KB of eden space. Or the 30 KB object can be allocated directly from the heap, and the thread can hope that the next object that is allocated will fit in the 25 KB of space that is still free within the TLAB. - By default, the size of a TLAB is based on three things: the number of threads in the application, the size of eden, and the allocation rate of threads. Hence two types of applications may benefit from tuning the TLAB parameters: applications that allocate a lot of large objects, and applications that have a relatively large number of threads compared to the size of eden. - What can be done instead is to monitor the TLAB allocation to see if any allocations occur outside of the TLABs. - Monitoring the TLAB allocation is another case where Java Flight Recorder is much more powerful than other tools. Figure 6-9 shows a sample of the TLAB allocation screen from a JFR recording. - In the open source version of the JVM (without JFR), the best thing to do is monitor the TLAB allocation by adding the -XX:+PrintTLAB flag to the command line. - The size of the TLABs can be set explicitly using the flag -XX:TLABSize=N (the default value, 0, means to use the dynamic calculation previously described). That flag sets only the initial size of the TLABs; to prevent resizing at each GC, add -XX:-ResizeTLAB (the default for that flag is true on most common platforms). This is the easiest (and, frankly, the only really useful) option for exploring the performance of adjusting the TLABs. - In the TLAB logging output, the refill waste value gives the current threshold for that decision: if the TLAB cannot accommodate a new object that is larger than that value, then the new object will be allocated in the heap. If the object in question is smaller than that value, the TLAB will be retired. - Applications that allocate a lot of large objects may need to tune the TLABs (though often using smaller objects in the application is a better approach). - Humongous - G1 region sizes G1 divides the heap into a number of regions, each of which has a fixed size. The region size is not dynamic; it is determined at startup based on the minimum size of the heap (the value of Xms). - The minimum region size is 1 MB. If the minimum heap size is greater than 2 GB, the size of the regions will be set according to this formula (using log base 2): region_size = 1 << log(Initial Heap Size / 2048); In short, the region size is the smallest power of 2 such that there are close to 2,048 regions when the initial heap size is divided. - the region size is always at least 1 MB and never more than 32 MB. - Less than 4 GB    1 MB  - Larger than 64 GB    32 MB  - The value given here should be a power of 2 (e.g., 1 MB or 2 MB); - G1 allocation of humongous objects If the G1 region size is 1 MB and a program allocates an array of 2 million bytes, the array will not fit within a single G1 region. But these humongous objects must be allocated in contiguous G1 regions. If the G1 region size is 1 MB, then to allocate a 3.1 MB array, G1 must find four contiguous regions within the old generation in which to allocate the array. (The rest of the last region will remain empty, wasting 0.9 MB of space.) - The humongous object will be collected during the concurrent G1 cycle. On the bright side, the humongous object can be freed quickly since it is the only object in the regions it occupies. Humongous objects are freed during the cleanup phase of the concurrent cycle (rather than during a mixed GC). - Because the heap could not be expanded to accommodate the new humongous object, G1 had to perform a full GC to compact the heap in order to provide the contiguous regions needed to fulfill the request, Without the additional logging provided by enabling PrintAdaptiveSizePolicy, the standard G1 GC log does not provide enough information to diagnose this situation. - A better next step is to reduce the size of those objects rather than tune the JVM around them. - G1 considers an object to be humongous if it will fill more than 50% of a region. - G1 regions are sized in powers of 2, starting at 1 MB. Heaps that have a very different maximum size than initial size will have too many G1 regions; the G1 region size should be increased in that case. - Applications that allocate objects larger than half the size of a G1 region should increase the G1 region size, so that the objects can fit within a G1 region. - Although the flag has been carried forward since those versions and is still present, it is no longer recommended (though it is not yet officially deprecated). The problem with this flag is that it hides the actual tunings it adopts, making it quite hard to figure out what the JVM is actually setting. - ergonomically - Some of the values it sets are now set ergonomically based on better information about the machine running the JVM, so there are actually cases where enabling this flag hurts performance. - scavenging - The AggressiveHeap flag is a legacy attempt to set a number of heap parameters to values that make sense for a single JVM running on a very large machine. - Values set by this flag are not adjusted as JVM technology improves, so its usefulness in the long run is dubious (even though it still is often used). # Cracking the Coding Interview, Fourth Edition: 150 Programming Interview Questions and Solutions - So how do you make yourself sound good without being arrogant? By being specific! - Consider an example: » Candidate #1: “I basically did all the hard work for the team ” » Candidate #2: “I implemented the file system, which was considered one of - the most challenging components because …” Candidate #2 not only sounds more impressive, but she also appears less arrogant - blabbers - When a candidate blabbers on about a problem, - Structure your responses using S A R : Situation, Action, Response - 3 Write pseudo-code first, but make sure to tell your interviewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you 4 Write your code, not too slow and not too fast - Step 1: Ask Questions Technical problems are more ambiguous than they might appear, so make sure to ask ques- tions to resolve anything that might be unclear or ambiguous You may eventually wind up - 0 and 130 How do we solve this? Just create an array with 130 elements and count the num- ber of ages at each value - APPROACH IV: BASE CASE AND BUILD Description: Solve the algorithm first for a base case (e g , just one element) Then, try to solve it for elements one and - permutations - NOTE: Base Case and Build Algorithms often lead to natural recursive algorithms # Java 8 Lambdas - Looking under the covers a little bit, the for loop is actually syntactic sugar that wraps up the iteration and hides it. - conflates what you are doing with how you are doing it. - long count = allArtists.stream()                        .filter(artist -> artist.isFrom("London"))                        .count(); - filter that build up the Stream recipe but don’t force a new value to be generated at the end are referred to as lazy. - Methods such as count that generate a final value out of the Stream sequence are called eager. - If we add the same printout to a stream that has a terminal step, such as the counting operation from Example 3-3, then we will see the names of our artists printed out (Example 3-6). - It’s very easy to figure out whether an operation is eager or lazy: look at what it returns. If it gives you back a Stream, it’s lazy; if it gives you back another value or void, then it’s eager. - Stream functions are lazy, you do need to use an eager operation such as collect at the end of a sequence of chained method calls. - Even the simplest application is still likely to have application code that could benefit from code as data. - It’s a good idea to use the primitive specialized functions wherever possible because of the performance benefits. - we map each track to its length, using the primitive specialized mapToInt method. Because this method returns an IntStream, we can call summaryStatistics, which calculates statistics such as the minimum, maximum, average, and sum values on the IntStream. - A BinaryOperator is special type of BiFunction for which the arguments and the return type are all the same. - you might conclude that this is a code smell - but compared to many other programming platforms, binary compatibility has been viewed as a key Java strength. - The Optional class lets you avoid using null by modeling situations where a value may not be present. - return albums.collect(groupingBy(album -> album.getMainMusician())); } - makes our intent much clearer using streams and collectors. - String result =     artists.stream()               .map(Artist::getName)               .collect(Collectors.joining(", ", "[", "]")); Here, we use a map to extract the artists’ names and then collect the Stream using Collectors.joining. This method is a convenience for building up strings from streams. - It lets us provide a delimiter (which goes between elements), a prefix for our result, and a suffix for the result. - public Map numberOfAlbums(Stream albums) {     return albums.collect(groupingBy(album -> album.getMainMusician(),                                      counting())); } This form of groupingBy divides elements into buckets. Each bucket gets associated with the key provided by the classifier function: getMainMusician. The groupingBy operation then uses the downstream collector to collect each - Each collector is a recipe for building a final value. - the boffins at Oracle have thought of this use case and provided a collector called mapping. - In both of these cases, we’ve used a second collector in order to collect a subpart of the final result. These collectors are called downstream collectors. In the same way that a collector is a recipe for building a final value, a downstream collector is a recipe for building a part of that value, which is then used by the main collector. - StringBuilder reduced =     artists.stream()            .map(Artist::getName)            .reduce(new StringBuilder(), (builder, name) -> {                    if (builder.length() > 0)                        builder.append(", ");                    builder.append(name);                    return builder;                }, (left, right) -> left.append(right)); reduced.insert(0, "["); reduced.append("]"); String result = reduced.toString(); I had hoped that last refactor would help us - some code that looks vaguely sane, - Collector is generic, so we need to determine a few types to interact with: The type of the element that we’ll be collecting, a String Our accumulator type, StringCombiner, which you’ve already seen The result type, also a String Example 5-25. How to define a collector over strings public class StringCollector implements Collector { A Collector is composed - String result =         artists.stream()                 .map(Artist::getName)                 .collect(Collectors.reducing(                     new StringCombiner(", ", "[", "]"),                     name -> new StringCombiner(", ", "[", "]").add(name),                     StringCombiner::merge))                 .toString(); This is very similar to the reduce-based implementation I covered in Example 5-20, which is what you might expect given the name. - public Artist getArtist(String name) {     return artistCache.computeIfAbsent(name, this::readArtistFromDB); } - the new compute and computeIfPresent methods on the Map interface are useful for these cases. - Method references are a lightweight syntax for referring to methods and look like this: ClassName::methodName. - Collectors let us compute the final values of streams and are the mutable analogue of the reduce method. - Map enhancements. Efficiently calculate a Fibonacci sequence using just the computeIfAbsent method on a Map. By “efficiently,” I mean that you don’t repeatedly recalculate the Fibonacci sequence of smaller numbers. - The changes to your code are surprisingly unobtrusive, - Concurrency arises when two tasks are making progress at overlapping time periods. Parallelism arises when two tasks are happening at literally the same time, such as on a multicore CPU. - The goal of parallelism is to reduce the runtime of a specific task by breaking it down into smaller components and performing them in parallel. - get-go. - you can call the parallelStream method in order to create a parallel stream from the get-go. Let’s look at a - public int serialArraySum() {     return albums.stream()                  .flatMap(Album::getTracks)                  .mapToInt(Track::getLength)                  .sum(); - We go parallel by making the call to parallelStream, as shown in Example 6-2; all the rest of the code is identical. Going parallel just works. Example 6-2. Parallel summing of album track lengths public int parallelArraySum() {     return albums.parallelStream()                  .flatMap(Album::getTracks)                  .mapToInt(Track::getLength) - The kinds of problems that parallel stream libraries excel at are those that involve simple operations processing a lot of data, such as simulations. - Monte Carlo simulations work by running the same simulation many times over with different random seeds on every run. - private void printResults() {         results.entrySet()                .forEach(System.out::println); - a -     private Runnable makeJob() {         return () -> {             ThreadLocalRandom random = ThreadLocalRandom.current(); - The streams framework deals with any necessary synchronization itself, so there’s no need to lock your data structures. - If a pipeline has calls to both parallel and sequential, the last call wins. - Packing Primitives are faster to operate on than boxed values. Number of cores The extreme case here is that you have only a single core available to operate upon, so it’s not worth going parallel. - The more time spent operating on each element in the stream, the better performance you’ll get from going parallel. - This gives us a good insight into what is going on under the hood without having to understand all the details of the framework. - private int addIntegers(List values) {     return values.parallelStream()                  .mapToInt(i -> i)                  .sum(); } Under the hood, parallel streams back onto the fork/join framework. - The fork stage recursively splits up a problem. Then each chunk is operated upon in parallel. Finally, the join stage merges the results back together. - Ideally, we want to spend as much of our time as possible in leaf computation work because it’s the perfect case for parallelism. - groups by performance characteristics: The good An ArrayList, an array, or the IntStream.range constructor. These data sources all support random access, which means they can be split up arbitrarily with ease. The okay The HashSet and TreeSet. You can’t easily decompose these with perfect amounts of balance, but most of the time it’s possible to do so. The bad Some data structures just don’t split well; for example, they may take O(N) time to decompose. Examples here include a LinkedList, which is computationally hard to split in half. Also, Streams.iterate and BufferedReader.lines have unknown length at the beginning, so it’s pretty hard to estimate when to split these sources. - Stateless operations need to maintain no concept of state over the whole operation; stateful operations have the overhead and constraint of maintaining state. If you can get away with using stateless operations, then you will get better parallel performance. - public static double[] parallelInitialize(int size) {     double[] values = new double[size];     Arrays.parallelSetAll(values, i -> i);     return values; } The - parallelPrefix operation, on the other hand, is much more useful for performing accumulation-type calculations over time series of data. It mutates an array, replacing each element with the sum of that element and its predecessors. I use the term “sum” loosely—it doesn’t need to be addition; it could be any BinaryOperator. - Data parallelism is a way to split up work to be done on many cores at the same time. - The five main factors influencing performance are the data size, the source data structure, whether the values are packed, the number of available cores, and how much processing time is spent on each element. - A wealth of material has been written on how to test and debug computer programs, - Test-Driven Development by Kent Beck - Growing Object-Oriented Software, Guided by Tests by Steve Freeman and Nat - The process of refactoring code to take advantage of lambdas has been given the snazzy name point lambdafication (pronounced lambda-fi-cation, practitioners of this process being “lamb-di-fiers” or “responsible developers”). - This antipattern can be easily solved by passing in code as data. Instead of querying an object and then setting a value on it, you can pass in a lambda expression that represents the relevant behavior by computing a value. - A key OOP concept is to encapsulate local state, such as the level of the logger. This isn’t normally encapsulated very well, as isDebugEnabled exposes its state. If you use the lambda-based approach, then the code outside of the logger doesn’t need to check the level at all. - ThreadLocal.withInitial(() -> database.lookupCurrentAlbum()); - when reading the code, the signal-to-noise ratio is lower. - This code smell crops up in situations where your code ends up in repetitive boilerplate - Even though test doubles are frequently referred to as mocks, actually both stubs and mocks are types of test double. The difference is that mocks allow you to verify the code’s behavior. The best place to understand more about this is Martin - supports our familiar friend: passing code as data. - artist.getName().startsWith("The"))            .map(artist -> artist.getNationality())            .peek(nation -> System.out.println("Found nationality: " + nation))            .collect(Collectors.toSet()); - a - a breakpoint can be set on the body of the peek method. In this case, peek can just have an empty body that you set a breakpoint in. Some debuggers won’t let you set a breakpoint in an empty body, in which case I just map a value to itself - The peek method is very useful for logging out intermediate values when debugging. - The critical design tool for software development is a mind well educated in design principles. It is not…technology. - As the Agile software movement has made testing of applications more important, the issues with the singleton pattern have made it an antipattern: a pattern you should never use. - macros. Did I say “lazy”? I meant focused on improving my productivity. - the command pattern. It’s frequently used in implementing component-based GUI systems, undo functions, thread pools, transactions, and wizards. - The strategy pattern is a way of changing the algorithmic behavior of software based upon a runtime decision. - An example algorithm we might want to encapsulate is compressing files. We’ll give our users the choice of compressing our files using either the zip algorithm or the gzip algorithm and implement a generic Compressor class that can compress using either algorithm. - Compressor zipCompressor = new Compressor(ZipOutputStream::new); zipCompressor.compress(inFile, outFile); - a - The observer pattern is another behavioral pattern that can be improved and - In the observer pattern, an object, called the subject, maintains a list of other objects, which are its observers. When the state of the subject changes, its observers are notified. It is heavily used in MVC-based GUI toolkits in order to allow view components to be updated when state changes in the model without coupling the two classes together. - The template method pattern is designed for these kinds of situations. Your overall algorithm design is represented by an abstract class. This has a series of abstract methods that represent customized steps in the algorithm, while any common code can be kept in this class. - a - As a bank, we’re going to be giving out loans to members of the public, companies, and employees. - We can start to model this in code with an abstract LoanApplication class that controls the algorithmic structure and holds common code for reporting the findings of the loan application. - What the template method pattern is really trying to do is compose a sequence of method calls in a certain order. - canonical - It’s usual to split up DSLs into two different categories: internal and external. - For example, Cascading Style Sheets (CSS) and regular expressions are commonly used external DSLs. - BDD is a variant of test-driven development (TDD) that shifts the emphasis onto talking about the behavior of the program rather than simply the tests that it needs to pass. - sneaky - been a bit sneaky here and used double braces at the beginning and end of the class definition: - public class StackSpec These start an anonymous constructor that lets us execute an arbitrary block of Java code, so it’s really just like writing out the constructor in full, but with a bit less boilerplate. I could have written the following instead: public class StackSpec {     public StackSpec() {         ...     } } There’s a lot more work involved in implementing a complete BDD - Every class or method in your program should have only a single reason to change. - This is part of the idea of a design exhibiting strong cohesion. A class is cohesive if its methods and fields should be treated together because they are closely related. If you tried to divide up a cohesive class, you would result in accidentally coupling the classes that you have just created. - So, we can use higher-order functions in order to help us easily implement the single responsibility principle. - Software entities should be open for extension, but closed for modification. — Bertrand Meyer - The overarching goal of the open/closed principle is similar to that of the single responsibility principle: to make your software less brittle to change. - Again, the problem is that a single feature request or change to your software can ripple through the code base in a way that is likely to introduce new bugs. - The open/closed principle is an effort to avoid that problem by ensuring that existing classes can be extended without their internal implementation being modified. - Its static withInitial method is a higher-order function that takes a lambda expression that represents a factory for producing an initial value. - This implements the open/closed principle because we can get new behavior out of ThreadLocal without modifying it. We pass in a different factory method to withInitial and get an instance of ThreadLocal with different behavior. - We can also generate completely different behavior by passing in a different lambda expression. - The term “immutability” can have two potential interpretations: observable immutability or implementation immutability. Observable immutability means that from the perspective of any other object, a class is immutable; implementation immutability means that the object never mutates. Implementation immutability implies observable immutability, but the inverse isn’t necessarily true. - A good example of a class that proclaims its immutability but actually is only observably immutable is java.lang.String, as it caches the hash code that it computes the first time its hashCode method is called. This is entirely safe from the perspective of other classes because there’s no way for them to observe the difference between it being computed in the constructor every time or cached. - There is no internal state to mutate, so they can be shared between different threads. - is fairly outmoded. - the open/closed principle is really just a usage of polymorphism. - Abstractions should not depend on details; details should depend on abstractions. - The goal of the dependency inversion principle is to allow programmers to write high-level business logic that is independent of low-level glue code. - So, we introduce an abstraction for reading information and an abstraction for writing information. The implementation of our accumulation module depends upon these abstractions. We can pass in the specific details of these implementations at runtime. This is the dependency inversion principle at work. In the context of - Example 8-44. The definition of withLinesOf private T withLinesOf(Reader input,                           Function, T> handler,                           Function error) {     try (BufferedReader reader = new BufferedReader(input)) {         return handler.apply(reader.lines());     } catch (IOException e) {         throw error.apply(e);     } } withLinesOf takes in a reader that handles the underlying file I/O. - Nonblocking I/O—or, as it’s sometimes called, asynchronous I/O—can be used to process many concurrent network connections without having an individual thread service each connection. - a - newline.splitAsStream(buffer.toString()) - newline. Conveniently, Java’s Pattern class has had a splitAsStream method added in Java 8 that lets us split a String using the regular expression and have a stream of values, consisting of the values between each split. - If you want to end your chain with a block of code that returns nothing, such as a Consumer or Runnable, then take a look at thenAccept and thenRun. - a - Transforming the value of the CompletableFuture, a bit like using the map method on Stream, can be achieved using thenApply. - When trying to figure out what is happening with your CompletableFuture, you can use the isDone and isCompletedExceptionally methods. - CompletableFuture is really useful for building up concurrent work, but it’s not the only game in town. - Reactive programming is actually a form of declarative programming that lets us program in terms of changes and data flows that get automatically propagated. - You can think of a spreadsheet as a commonly used example of reactive programming. If you enter =B1+5 in cell C1, it tells the spreadsheet to add 5 to the contents of cell B1 and put the result in C1. - A CompletableFuture represents an IOU for a value. They can be easily composed and combined using lambdas. - Unfortunately, over the years Java has acquired a bit of a reputation as a staid development choice that has failed to evolve with the times, in part because it has been popular for a long period of time; familiarity # Java Generics and Collections - reputed - Einstein is reputed to have said, “Everything should be as simple as possible but no simpler”. - sparked some controversy. - roundabouts: - reify - Newton is reputed to have said, “If I have seen farther than others, it is because I stand on the shoulders of giants”. - As Hamming said of computer scientists, “Instead of standing on each other’s shoulders, we stand on each other’s toes.”) - increased use of collections in favor of arrays. In Part II, we describe - a problem known as code bloat. - Why does the argument have type List and not List? Because type parameters must always be bound to reference types, not primitive types. - Look Out for This! One subtlety of boxing and unboxing is that == is defined differently on primitive and on reference - So both of the following assertions succeed using Sun’s JVM: List bigs = Arrays.asList(100,200,300); assert sumInteger(bigs) == sum(bigs); assert sumInteger(bigs) != sumInteger(bigs); // not recommended In the - example, we have the following: List smalls = Arrays.asList(1,2,3); assert sumInteger(smalls) == sum(smalls); assert sumInteger(smalls) == sumInteger(smalls); // not recommended This is because 6 is smaller than 128, so boxing the value 6 always - exactly the same object. In general, it is not specified whether boxing the same value twice should return identical or distinct objects, so the inequality assertion shown earlier may either fail or succeed depending on the implementation. Even for small values, for which - It is clearer and cleaner to use equals rather than == to compare values of reference type, such as Integer or String. - The foreach loop can be applied to any object that implements the interface Iterable (in package java.lang), which in turn refers to the interface Iterator (in package java.util). - public static List toList(T[] arr) { List list = new ArrayList(); for (T elt : arr) list.add(elt); return list; - This is indicated by writing at the beginning of the method signature, which declares T as a new type variable. A method which declares a type variable in this way is called a generic method. - The vararg feature permits a special, more convenient syntax for the case in which the last argument of a method is an array. To use this feature, we replace T[] with T… in the method declaration: - public static List toList(T... arr) { List list = new ArrayList(); for (T elt : arr) list.add(elt); return list; } } Now the method may be invoked as follows: List ints = Lists.toList(1, 2, 3); List words = Lists.toList("hello", "world"); This is just shorthand for - We clarify our code by liberal use of the assert statement. - Java, one type is a subtype of another if they are related by an extends or implements clause. - Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. - Substitution Principle: a variable of a given type may be assigned a value of any subtype of that type, and a method with a parameter of a given type may be invoked with an argument of any subtype of that type. - Substitution Principle, if we have a collection of numbers, we may add an integer or a double to it, because Integer and Double are subtypes of - List is not a subtype of List, and - where List is a subtype of itself, and we also have that List is a subtype of Collection. - (because List is a subtype of List), - In general, if a structure contains elements with a type of the form ? extends E, we can get elements out of the structure, but we cannot put elements into the structure. - List, which is a subtype of List (since Integer is a subtype of Number, as required by the extends wildcard). - Always use wildcards where you can in a signature, - The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don’t use a wildcard when you both get and put. - In Java, array subtyping is covariant, meaning that type S[] is considered to be a subtype of T[] whenever S is a subtype of T. - In contrast, the subtyping relation for generics is invariant, meaning that type List is not considered to be a subtype of List, except in the trivial case where S and T are identical. - Wildcards reintroduce covariant subtyping for generics, in that type List is considered to be a subtype of List when S is a subtype of T. Here is a third variant of the fragment: List ints = Arrays.asList(1,2,3); List nums = ints; nums.set(2, 3.14); // compile-time error assert ints.toString().equals("[1, 2, 3.14]"); // uh oh! - The assignment violates the Get and Put Principle, because you cannot put a value into a type declared with an extends wildcard. - Wildcards also introduce contravariant subtyping for generics, in that type List is considered to be a subtype of List when S is a supertype of T (as opposed to a subtype). - Detecting problems at compile time rather than at run time brings two advantages, one minor and one major. The minor advantage is that it is more efficient. The system does not need to carry around a description of the element type at run time, and the system does not need to check against this description every time an assignment into an array is performed. The major advantage is that a common family of errors - not significant and elements may not be repeated), and a number of representations are available, including arrays, linked lists, trees, and hash tables. - Nonetheless, there are a few cases where arrays are preferred over collections. Arrays of primitive type are much more efficient since they don’t involve boxing; and assignments into such an array need not check for an array store exception, because arrays of primitive type do not have subtypes. - Following Leanpub’s motto “Publish Early, Publish Often”, I - the new Date and Time API (application program interfaces), feel quite familiar and can be used immediately by an experienced Java developer. # Misc - The intent of the SINGLETON pattern is to ensure that a class has only one instance and to provide a global point of access to it. - Don’t let SINGLETONs become a fancy way to create global variables. The - I can help you avoid some of the hidden coral reefs that lie beneath the Sea of Apple, and help you find the fair winds to keep your sails full. - No language is perfect, but some are excellent. - with the goal of bringing object-oriented and functional programming into one coherent whole. - Clojure embodies a powerful vision for how programming should be done. - I assume that you are well versed in object-oriented programming and you can read Java code. - I hope you find functional programming as seductive as I did. - chunks of code - a significant amount of example code - programming is a better fit for many of the unique challenges of our time, - both FP and OOP are tools, not panaceas. - can saturate CPU resources - Java NIO instead of blocking java.net.Socket may also improve an application’s performance by - test that your methods behave properly when passed negative, zero, and positive values for each numerical parameter. - The problem is easy to fix. Simply compare i % 2 to 0 rather than to 1, and reverse the sense of the comparison: public static boolean isOdd(int i) {     return i % 2 != 0; } - If you are using the isOdd method in a performance-critical setting, you would be better off using the bitwise AND operator (&) in place of the remainder operator: public static boolean isOdd(int i) {     return (i & 1) != 0; } - The second version may run much faster than the first, depending on what platform and virtual machine you are using, and is unlikely to run slower. As a general rule, the divide and remainder operations are slow compared to other arithmetic and logical operations. - It's a bad idea to optimize prematurely, - In summary, think about the signs of the operands and of the result whenever you use the remainder operator. - not all decimals can be represented exactly using binary floating-point. - If you are using release 5.0 or a later release, you might be tempted to fix the program by using the printf facility to set the precision of the output: - Binary floating-point is particularly ill-suited to monetary calculations,