real world DB deadlock reduction — insert hotspot

One of my multi-threaded java apps (using ExecutorSerivce) started getting database deadlocks when I increased thread count from 1 to 5.

* In Dev/Test environment, i got up to 4 deadlocks out of 20,000-40,000 inserts.
* In Production, I got 3000+ deadlocks out of 20,000 inserts.

Solution: I changed the clustered index from the table’s identity col to an AccountNumber column.

Result? down to below 5 deadlocks.

Analysis: Probably the clustered index on identity col created a hotspot for inserts. Since new rows all get similar identity values, all 5 threads need to write to the same data pages (sybase defaults to page lock). Each thread (with its own db connection and spid) in the deadlock probably writes to 2 pages within on transaction. If one thread already wrote on page 1 and needs to write on page 2 before commit(), but the other thread already wrote to page 2 and needs page 1, then this scenario meets

* wait-for circle
* incremental lock acquisition
* mutex
* non-preemption

financial jargon: buy-side, sell-side

http://en.wikipedia.org/wiki/Buy_side:

The split between the Buy and Sell sides should be viewed from the perspective of securities exchange services. The investing community must use those services to trade securities. The “Buy Side” are the buyers of those services; the “Sell Side” are the sellers of those services.

Sell side brokerages are registered members of a stock exchange, and required to be market makers in a given security. Buy side firms usually take speculative positions or make relative value trades. Buy side firms participate in a smaller number of overall transactions, and aim to profit from market movements and accruals rather than through risk management and the bid-offer spread.

In Short the entity paying the commission on trade would be a buy side and the one receiving it is a sell side.

threadpool && GUI examples, showcasing anon class

Get used to this kind of coding style. In this case I don’t see a good reason for the anon class. It’s more readable to pull it out into a named static nested (or top-level) class.

However, in real life the anon class’s methods often need the variables in the enclosing class. Anon is quick and dirty.


public static void main1(String args[]) {
new ScheduledThreadPoolExecutor(1).scheduleAtFixedRate(new Runnable() {
public void run() {
System.out.println(new Date());
}
}, 0, 1000, TimeUnit.MILLISECONDS);
}

// Now see the same pattern in this GUI code:

ActionListener taskPerformer = new ActionListener() {
public void actionPerformed(ActionEvent evt) {
//...Perform a task...
}
};
new Timer(delay, taskPerformer).start();

find the first lonewolf in an array

Q: if an integer appears only once in an array, then it’s a lone wolf. Find the first lone wolf in a given array.

one idea — reverse scan the array and find the last unique element.

one idea — forward scan the array.
* any “new” element will be appended to a LinkedHashMap and painted green
* any “seen” element will be repainted brown
* How to test for newness? Any examined element is tested by contains() against the green/brown collection.
* at end of the scan, return 1st green.

one idea — forward scan the array.
* any “new” element will be appended to a green LinkedHashSet
* any “seen” element will be moved from green into a brown HashSet
* How to test for newness? Any element is tested by contains() against the green and the brown.
* at end of the scan, return 1st green.

sorted list, briefly

I was asked about a sorted list’s performance of
* add()
* find() by key
* return all elements in sorted order

These 2 operations are equally frequent.

I could only think of 2 types of sorted list(???)
LL) sorted linked list
AL) sorted array list — based on an expandable array
How about 3) linkedHashMap where the value is either a count or a linked list of the identical objects.

FIND will be slow for LL — no random access, so this is not suitable.

AL’s add() requires O(log(n)) to locate the position to insert, but also O(n) to shift lots of existing occupants. Average shift complexity is n/2 i believe. By the way remove() would also require shifting.

const ^ input iterator – unrelated

(It’s probably enough to know when to use each… Tbudget?)

A) input iterator is a fwd iterator for input streams — P802 [[Absolute C++]] (This book has concise coverage of const and input iterators)

B) const iterator is modeled on ptr-to-const, so you can’t make *myIterator a LHS

These 2 are unrelated.

Are these real (template) classes? dummy types or typedef? I feel in general you can’t say for sure, so I assume the lowest common denominator — dummy types. Note const_iterator is a nested Type in container class declarations, but still it can be a real class, dummy type or typedef.