New SMR design

So! I don’t think this idea works, because to make it work the performance would be too poor, but…

You have a main state, and a per-thread state.

Each per-thread state registers with the main state.

The main state holds a counter, the “current counter”, which begins at 0. Every time a thread adds an element to its reuse candidate list, it stores in the reuse candidate the value of the main counter, and atomically increments the main counter. (On a busy system, the contention on that counter would drive performance into the ground – however, there is a scalable counter design…)

There is another counter in the main state, the “safe counter”, which also begins at 0 – it begin safe to reuse elements up to this value.

Every time a thread exits a read section, it stores the current value of that main counter in its thread state.

When we come to check to see if we can advance the safe counter, we iterate over the thread states, looking at their counter (the value of the main state current counter when they last exited a read section), and find the lowest value of them all (ignore idle threads for a moment). We then advance the safe counter to this lowest value – i.e. this is the point after which not all threads have exited a read section, and so the reuse candidates cannot yet be reused.

To deal with idle threads, we keep a flag in the thread state, which is raised when the thread enters a read section and lowered when we check to advance the safe counter. If the flag is lowered, then the thread has been idle.

In conceptual terms, ignoring actual practial performance, the design has high fidelity with regard to knowing which elements can be reused. As each element has its own generation count, and we know to which generation count we’re safe to re-use elements, we reuse every possible element we can.

What strikes me now though is that perhaps another way is to invert the paradym; rather than assuming we can’t advance, and then checking to see how far it is safe to advance (and so having trouble with idle threads, since they are silent), what about assuming we can advance (and so idle threads naturally say the right thing), with blockers in the way for the points beyond which we cannot advance?

Have to think about this, might just be crazy in the first instance, will see.

SMR Redux

So, my previous post about a design flaw in SMR, was incorrect.

Where I’d not touched that code for a while, I was not fully understanding what was going on. In fact, the code knows that a thread has at any time in the past (since the most recent generation advance) exited a read section, and so is not dependent on checking at a moment when no threads are in read sections.

So, I’ve been working on the tests, getting them to work, and I’ve finally come to a test which is really using SMR in anger, and of course this reveals to you what it’s like to actually use the API – where that API has changed, and is now no longer called every now and then when entering/exiting a read section or submitting an element, but explicitly and manually by the user.

One inherent aspect of SMR, which is visible and awkward for the developer, is that it is never possible to guarantee that an attempt to advance the generation counter will work. Another thread which is inside a read section blocks the advance of the generation counter beyond its current value. Of course, read sections are by design intended to be extremely brief, so in practise it’s not an issue – but it does mean no guarantee.

One thing which has become clear is that the function call which attempts to advance the generation counter has to be multi-threaded – it is ugly and onerous to put upon the user the burden of ensuring this is only called by a single thread at a time.

SMR

So I’ve been going through the tests making them work again.

I’m currently working on SMR.

Having not touched the SMR code for some time I come back to it fresh – and I have perceived what I think is a design flaw. Not a bug, it works, but, well, maybe it doesn’t work very well when load is high.

The core issue with SMR is knowing when it’s safe to advance the generation counter. Each SMR instantiation maintains a generation counter, which begins at 0, and when an allocation is submitted to SMR (to be returned when it is safe to reuse or free, i.e. when no thread could possibly access it) it is assigned the value at that time of the generation counter.

When the generation counter has advanced by *two* more than the value in an allocation (I can’t remember why two, offhand – there is a vital reason for it, or there was at any rate, as I initially had it set to one, and that was a bug; I realised why and changed it to two) then it is safe to be reused.

Now, the design flaw is this : to advance the generation counter, the user calls an SMR function, which checks for certain criteria (I’ll come to that in just a mo) and if they are satisfied, the generation counter is advanced.

Remember here we’re checking for the possibility of a thread accessing an element which has already been by one thread submitted to SMR for reuse – i.e. that thread has emerged from a read section holding the element, having removed it probably from a data structure, and wants it to be re-used. The problem SMR is solving is that other threads might be engaged at that very moment in lock-free work and hold pointers to that element. We need all threads to be known to have exited their read sections (the code which does lock-free work) or to have been idle.

The critera are that since the last call to this function, all threads have either been idle (which is to say, not entered a read section – i.e. have done no lock-free work), or have entered and then exited a read section. If however any thread is currently IN a read section, then it could be it holds a pointer to this allocation.

So the problem is this – if the data structure is very busy, and there are many threads, some threads will always or almost always be in a read section. We never get to advance the generation counter!

A solution which comes to mind is this : each thread in its per-thread SMR state keeps track of the number of tiems it has entered and exited a read section. It also keeps a copy of the values of those counters from when the user last checked to see if the generation counter could be advanced.

This way even if we have lots of busy threads, we can still advance the generation counter, becuse we can see *how often each thread has exited a read section*. So even if many threads are currently IN a read-section, we can still know it’s safe to advance the ccounter.

So now I have more work to do – in the sense that I need to make the current SMR pass it tests again (which is itself already quite improved since the benchmark app was working), get the benchmark app running again, benchmark, then make these changes, then benchmark again.

Progress

Ha. My post has the same name as a Russian spaceship.

A weekend ago I made liblfds compile again.

I’m now working on the test suite. It’s a lot of work. I’m going to release without the benchmark programme – it’ll just take too long.

So, current goal is to get test compiling.

I’d like to get it done this weekend, but we’ll see.

Managed to really bang a little toe into a metal bar, yesterday, so I’m stuck indoors today (and prolly tomorrow). There’s a Statue of Liberty kayak trip this Sunday, which by my trip up to WDC Thu/Fri I completely forgot to book in time – uber bleh :-( like the third time I’ve missed it, and it only runs every two weeks.

The Hubris of Apple

Well, it took about eight, nine hours, but I finally have command line loading of music files into an iPod Shuffle 4th gen.

iTunes is as much a vastly bloated monstrousity as I remembered it to be from about six, seven years ago. The hubris here is beyond the pale – to load music into your device when you plug it in, Apple has arranged to have no less than three seperate processes running *permanently* on your PC. The iTunes installer – for the software for what is at the core of it copying an mp3 file from one device to another – 149mb. It actually installed no less than *six* seperate programmes.

I’m pleased with the audio quality of the 4th gen. I took a risk buying it. I was going to go for a new-in-box (but old, obviously) first gen, but the problem is the batteries age even without being used – the battery on it was probably shot, or not far from it. It is possible to buy a replacement battery and motherboard (they’re soldered together) but it’s quite difficult to dismantle the first gen for the swap.

WU sign-up apparently broken in Chromium

Well, in a field consisting of the impossible, the appalling, the broken and the catastrophic, WU seemed least worse.

I signed up.

Ah.

No.

I tried to sign up.

Turns out their sign-up form doesn’t work in Chromium.

You fill it all in, hit submit and… nothing happens at all.

They have form in this matter. If you try to view the site in FF with DOM storge off and cookies off, it doens’t even render the page. Also in Chromium (which is normal – cookies on, etc) the link to talk to customer support doesn’t work.

What can you say?

So I still can’t transfer money from one country to another. I came into this with expectations, and the actuality is zero. Nothing, nada, doesn’t work, can’t be done. What I need, on an emotional level, is an expectations reset. The problem is I keep *thinking* things *ought* to be how they *ought* to be. Hope springs eternal.

Western Union UI fail / bait’n’switch?

wu_summary

See this? it’s from the Western Union site. See the USD value? that’s the amount I’m sending. See the SEK value? that’s the amount which will arrive. See the exchange rate? that’s the exchange rate.

…oh no it’s not.

That’s the MARKET exchange rate – the inter-bank rate for transfers of over 5m USD.

The ACTUAL rate WU would use (I spent 10 mins finding out from on-line help) is about 8.2.

The thing is, the SEK value there IS for the rate WU will use – not the market rate.

A totally incompetent or deliberately deceptive UI.

Western Union

I’ve been trying for two months now to make a money transfer from the USA to Sweden.

It’s actually impossible, at least on terms I would find acceptable – i.e. not being obscenely and stupidly ripped off, or having my intelligence insulted, etc.

I’m currently (still – because changing to a decent bank, also impossible) with Bank oF America, who charge 45 USD a transfer (only 35 if you let them do the currency conversation – which will cost me about 90 USD compared to the destination bank).

I looked at online foreign exchange brokers, but the amount of information they want to know about you, to open an account, is obscene. Most of them bait’n’switch, too, so you don’t find out until you’re well into the application process.

I looked at Bitcoin, but in Sweden, the banks there got together and make a nice, effective on-line and mobile payment system – and screwed up joining in if you’re overseas. I can’t join – I can in theory, but they rely on international short-code SMS for joining, and it doesn’t work. (I had hell talking to T-Mobile and Swedbank to try to get it sorted out. Give Swedbank credit, I received an email from them this morning saying they thought they might have fixed it. They hadn’t, but at least it seems they’re trying).

Because this system of theirs is so popular, everyone buying Bitcoin uses it to pay. So I can’t sell Bitcoin in Sweden (or the Nordics in general).

I looked at Western Union. They looked alright – the cost beat Bank oF America by 50 USD, and I could do this on-line (unlike BoA, who with charge 45 USD per thousand transfered, the justification (and this is some serious jive-crack gibbering madness) being security, and so with them I have to go into a branch), so I went for it…

…only to find out the maximum transfer is 5k USD. I want to transfer 5.5k. I really do not want to pay a second 150 USD or so, to transfer that 500 USD extra.

There was a note on the site that higher values could be transfered if the transfer is made in person, so I went over today to a WU agent which is on the block, in a supermarket.

I asked the transfer limit to Sweden.

She replies that she didn’t know, that it was whatever the computer said, and I would be better off going to the nearest WU shop and asking there.

In other words, rather than her operating the computer so she could tell me, she wanted me to leave the store, work out direction to the WU shop a metro stop away, spend about two hours all told going there and back and spending six bucks on transfer, *so I could ask them rather than her*.

I left.

I would email WU and let them know… but they won’t care either, in exactly the same way. Why should they? this woman, the people working for WU whom I might write to (if the have actually arranged their site so you can write to them – it’s very rarely so, IME), none of them care, because *it’s just more work and they get nothing for it*.

Apple Store

I have – possibly had – a first generation iPod shuffle. The second I’ve owned in fact; the audio quality is superb, far far in advance of the second gen, and the third gen had the headphone design issue (volume control in the headphone cable – I have my own ER-4Ps).

However, it’s getting a bit flakey – reluctant to start – and I think it might just this morning have died.

I had to go up into town today, pick up shirts, so I thought I’d stop by the Apple Store to try my headphones in the fourth generation unit.

That was my first mistake. A shop, in the high street.

So I head on up into town, hop out, walk in.

This is the first time I’ve been in an Apple Store.

Speaking as a software engineer, I think there’s a big design flaw; the interior of the store is a range of desks, nice wooden desks, with product on. They’re surrounded by people, so they’re hard to see at a distance, and they have a little low sign on them in the middle, about 20cm high, which you can only read if you’re close enough to already be able to see the product on that table.

So if you’re looking for something in particular, you have to scout the whole store, which I did, but iPod shuffles are small, so I couldn’t find them.

I asked a guy. “Over there, by that woman, she can help you.”

I go over there.

“Do you have one I can listen to?”, I ask.

“Yes, here, on the top.”

I unpacked my headphones, plug them in and turn the unit on. Or rather I moved the little switch which ought to turn the unit on. Nothing. I play with it for a while – volume controls, on and off again, the usual. Nothing.

There’s one unit on there which you can lift and heft. There’s another six or seven which are glued onto the stand. I try a couple of them. Also nothing.

“It’s not working.”

To this, she comes out with some jive-crack insanity; “yes, it’s probably because the other units are on demo mode and so there’s too many.”

(She means the iPod nanos which are next to it and turned on and obviously so, as they have a screen which it lit up and in demo mode. They are absolutely and in every way unconnected and unrelated to the shuffles).

What’s actually happened, I would say, is that the units are all out of power. This isn’t the case for the nanos, because they have a screen and a demo mode and so it’s clear when they’re dead. The shuffles have no display of any kind, and so they’re dead.

I will now paraphrase the rest of the unspoken conversation.

“So, you expect me to buy this personal music player – without having listened to it first.”

“Yes.”

“Goodbye.”

The basic problem of course is that she just doesn’t care. She is discouraged from caring. If she raised the issue, she’d have to do the work to fix it and get nothing for having done so. This problem of course is inherent in modern company design and so endemic throughout industry.

Status

Have made the gross code changes to liblfds, now need to slap it around until it compiles.

Then need to rewrite all the tests, and also the benchmark app too.

This thing has one hell of a tail. I need an automatic code adjuster, something which understands C and adheres to my code style; but that won’t help with test or benchmark.